锐客网

  1. 首页 > it技术 > >

（Div.2）D.|（Div.2）D. Edge Deletion

传送门
学习来自于：http://www.cnblogs.com/Lubixiaosi-Zhaocao/p/9951711.html
【（Div.2）D.|（Div.2）D. Edge Deletion】题目大意：
一个无向图，各点到点1的最短距离为di，保证满足条件删除m-k条边之后使得到点1的距离仍为di的点数量最多的情况下，输出剩余的k条边的编号（输入顺序即编号）
思路：
因为都是和1的最短距离，是单源最短路，所以应该会用到Dijkstra算法，但是他要输出剩余的k条边，这里可以用一个bfs，贪心从1号开始取和以1号为前驱为最短距离的边，然后再将这条边的另一个节点加入队列。所以在跑Dijkstra时，要保存到点i最短路的前驱father[i], 最后就是在这一颗由最短路构成的树上bfs

//#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF=LONG_LONG_MAX; const ll inf=LONG_LONG_MIN; const ll maxn=3e5+5; ll n,m,k; struct node { ll p; //当前点 ll dis; //到改点的距离 node(ll np=0,ll ndis=0) { p=np,dis=ndis; } bool operator <(const node& x)const { return dis>x.dis; } }; struct edge { ll id; ll to; ll w; edge(ll nid=0,ll nto=0,ll nw=0) { id=nid,to=nto,w=nw; } }; ll father[maxn],faedge[maxn]; vector e[maxn]; bool vis[maxn]; ll dist[maxn]; void Dijkstra() { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[1]=0; father[1]=1; priority_queue q; q.push(node(1,0)); while(!q.empty()) { node tmp=q.top(); q.pop(); int np=tmp.p; if(vis[np]) continue; else { vis[np]=1; for(int i=0; idist[np]+nw) { dist[nto]=dist[np]+nw; father[nto]=np; //记录nto的前驱 （相当于父亲 faedge[nto]=nid; //并记录nto的前驱边 q.push(node(nto,dist[nto])); } } } } } vector ans; vector son[maxn]; void bfs() { queue q; q.push(1); while(!q.empty()&&k>0) { int tmp=q.front(); q.pop(); for(int i=0; i0) { ans.push_back(faedge[v]); q.push(v); k--; } else { break; } } } } int main() { scanf("%lld%lld%lld",&n,&m,&k); ll x,y,w; for(int i=1; i<=m; ++i) { scanf("%lld%lld%lld",&x,&y,&w); e[x].push_back(edge(i,y,w)); e[y].push_back(edge(i,x,w)); } Dijkstra(); for(int i=2; i<=n; i++) { son[father[i]].push_back(i); //将父亲关系转化成儿子关系 } bfs(); cout<

不写这个我都快把最短路给忘了

    推荐阅读


    上一篇：[bzoj3462]dzy loves math II 解题报告

    下一篇：呐呐