Codeforces 1076D——最短路算法

题目

给你一个有n个顶点、m条边的无向带权图。需要擦除一些边使得剩余的边数不超过k，如果一个点在原始图到顶点1的最短距离为d，在删边后的图中到顶点的最短距离仍是d,则称这种点是 good。问如何删边，使得 good点最多。

分析

首先调用最短路算法求各点到顶点1的最短距离，同时记录下每点在最短路上的前一个顶点。然后从顶点1出发搜索一个大小为k的联通块即可（如果够k个）

代码

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

参考链接：https://blog.csdn.net/SparkFucker/article/details/84024243