（Div.2）D. Edge Deletion

传送门

学习来自于：http://www.cnblogs.com/Lubixiaosi-Zhaocao/p/9951711.html

题目大意：

一个无向图，各点到点1的最短距离为di，保证满足条件删除m-k条边之后使得到点1的距离仍为di的点数量最多的情况下，输出剩余的k条边的编号（输入顺序即编号）

思路：
因为都是和1的最短距离，是单源最短路，所以应该会用到Dijkstra算法，但是他要输出剩余的k条边，这里可以用一个bfs，贪心从1号开始取和以1号为前驱为最短距离的边，然后再将这条边的另一个节点加入队列。所以在跑Dijkstra时，要保存到点i最短路的前驱father[i], 最后就是在这一颗由最短路构成的树上bfs

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
#include<limits.h>
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<edge> 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<node> 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; i<e[np].size(); ++i) {
edge ne=e[np][i];
ll nto=ne.to;
ll nw=ne.w;
ll nid=ne.id;
if(dist[nto]>dist[np]+nw) {
dist[nto]=dist[np]+nw;
father[nto]=np; //记录nto的前驱 （相当于父亲
faedge[nto]=nid; //并记录nto的前驱边
q.push(node(nto,dist[nto]));
}
}
}
}
}
vector<int> ans;
vector<int> son[maxn];
void bfs() {
queue<int> q;
q.push(1);
while(!q.empty()&&k>0) {
int tmp=q.front();
q.pop();
for(int i=0; i<son[tmp].size(); ++i) {
int v=son[tmp][i];
if(k>0) {
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<<ans.size()<<endl;
for(int i=0; i<ans.size(); ++i) {
cout<<ans[i]<<' ';
}
cout<<endl;
return 0;
}

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

最后

以上就是彩色心情为你收集整理的（Div.2）D. Edge Deletion的全部内容，希望文章能够帮你解决（Div.2）D. Edge Deletion所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。