Codeforces|Codeforces 1076D——最短路算法 Codeforces1076D——最短路算法

题目
给你一个有n个顶点、m条边的无向带权图。需要擦除一些边使得剩余的边数不超过k，如果一个点在原始图到顶点1的最短距离为d，在删边后的图中到顶点的最短距离仍是d,则称这种点是 good。问如何删边，使得 good点最多。
【Codeforces|Codeforces 1076D——最短路算法】分析
首先调用最短路算法求各点到顶点1的最短距离，同时记录下每点在最短路上的前一个顶点。然后从顶点1出发搜索一个大小为k的联通块即可（如果够k个）
代码

1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 typedef long long ll; 9 10 const ll INF = (ll)1 << 61; 11 const int maxv = 300000 + 10; //最大顶点数 12 const int maxe = 300000 * 2+ 10; //最大边数 13 ll dis[maxv]; //源到各顶点的最短距离 14 int vis[maxv]; //记录是否被收录，用来代替集合S 15 int head[maxv]; //采用链式前向星建图 16 int pre[maxv]; //最短路树，记录前一个节点 17 18 vectorans; //记录答案 19 int n, m, k; //顶点数、边数、最大保留的边数 20 21 struct Node 22 { 23int u; 24ll d; //该节点的编号与距离 25bool operator < (const Node x) const 26{ 27returnd > x.d; 28} 29 }; 30 31 struct Edge 32 { 33int to, w, next; 34 }edge[maxe]; 35 36 37 inline void addedge(int u, int v, int w, int id) 38 { 39edge[id].to = v; 40edge[id].w = w; 41edge[id].next = head[u]; 42head[u] = id; 43 } 44 //s为起点 45 void Dijsktra(int s) 46 { 47priority_queueq; //取出集合T中的最小值 48memset(vis, 0, sizeof(vis)); 49memset(pre, -1, sizeof(pre)); 50//memset(dis, INF, sizeof(dis)); //与邻接矩阵不同，这里初始化为INF就可以，原因自己想 51for (int i = 0; i <= n; i++)dis[i] = INF; 52 53dis[s] = 0; 54q.push(Node{ s, dis[s] }); 55while (!q.empty()) 56{ 57Node x = q.top(); q.pop(); 58int u = x.u; 59 60if (vis[u])continue; 61 62vis[u] = true; 63for (int i = head[u]; i != -1; i = edge[i].next)//松弛与u直接相邻的顶点 64{ 65int v = edge[i].to; 66int w = edge[i].w; 67if (!vis[v] && dis[u] + w < dis[v]) 68{ 69dis[v] = dis[u] + w; 70pre[v] = u; //记录最短路树的父节点 71q.push(Node{ v,dis[v] }); 72} 73} 74} 75 } 76 77 //从s出发找出最短路树上的k个节点（不到k个就是全部节点） 78 void bfs(int s) 79 { 80queueq; 81q.push(s); 82while (!q.empty()) 83{ 84int u = q.front(); q.pop(); 85for (int e = head[u]; e != -1; e = edge[e].next) 86{ 87int v = edge[e].to; 88if (pre[v] == u && ans.size() < k) 89{ 90q.push(edge[e].to); 91ans.push_back(e / 2 + 1); //无向边建图时存了两遍，真实序号位e/2+1 92} 93} 94if (ans.size() >= k)break; 95} 96 } 97 98 int main() 99 { 100while (scanf("%d%d%d",&n,&m,&k) == 3) 101{ 102memset(head, -1, sizeof(head)); 103int id = 0; 104for (int i = 0; i < m; i++) 105{ 106int u, v, w; 107scanf("%d%d%d", &u, &v, &w); 108addedge(u, v, w,id++); addedge(v, u, w,id++); 109} 110 111Dijsktra(1); 112 113ans.clear(); 114bfs(1); 115int cnt = ans.size(); 116printf("%d\n", cnt); 117for (int i = 0; i < cnt; i++) 118printf("%d%c", ans[i], i == cnt - 1 ? '\n' : ' '); 119} 120return 0; 121 }

参考链接：https://blog.csdn.net/SparkFucker/article/details/84024243
转载于:https://www.cnblogs.com/lfri/p/9955200.html