Educational Codeforces Round 54 (Rated for Div. 2) D:Edge Deletion

题目链接：http://codeforces.com/contest/1076/problem/D

题意：给一个n个点,m条边的无向图。要求保留最多k条边，使得其他点到1点的最短路剩余最多。

思路：当找到单源最短路后，将其转换为一个所有点到点1都是最短路的树状结构，利用贪心确定所要保留的K条边（找离根最近的边，利用BFS）。

代码：

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <queue>
  8 #include <set>
  9 #include <map>
 10 #include <stack>
 11 #define ll long long
 12 //#define local
 13 
 14 using namespace std;
 15 
 16 const int MOD = 1e9+7;
 17 const int inf = 0x3f3f3f3f;
 18 const double PI = acos(-1.0);
 19 const int maxn = 3e5 + 10;
 20 const int maxedge = 3e5 + 10;
 21 
 22 struct qnode {
 23     int v;
 24     ll c;
 25     qnode(int v=0,ll c=0) : v(v), c(c) {}
 26     bool operator < (const qnode &r)const {//priority_queue 默认从大到小排列
 27         return c > r.c;
 28     }
 29 };
 30 
 31 struct Edge {
 32     int v, w, pre;
 33 } edge[maxedge*2];
 34 
 35 int point[maxn]; //point[i] = -1
 36 int cnt;
 37 bool vis[maxn]; // already init in the dijkstra
 38 ll dist[maxn]; // already init in the dijkstra, overflow!
 39 vector <int> v1[maxn];
 40 vector <int> v2[maxn];
 41 struct Path {
 42     int u, e;
 43 }path[maxn];
 44 
 45 void AddEdge(int u, int v, int w) {
 46     edge[cnt].v = v;
 47     edge[cnt].w = w;
 48     edge[cnt].pre = point[u];
 49     point[u] = cnt++;
 50 }
 51 
 52 void Dijkstra(int n,int start) {
 53     memset(vis,false,sizeof(vis));
 54     memset(dist, 0x3f, sizeof(dist));
 55     priority_queue <qnode> que;
 56     while(!que.empty()) que.pop();
 57     dist[start] = 0;
 58     que.push(qnode(start, 0));
 59     qnode tmp;
 60     while(!que.empty()) {
 61         tmp = que.top(); que.pop();
 62         int u = tmp.v;
 63         if(vis[u]) continue;
 64         vis[u] = true;
 65         for(int i = point[u]; i != -1; i = edge[i].pre) {
 66             int v = edge[i].v;
 67             int w = edge[i].w;
 68             if(!vis[v] && dist[v]>dist[u]+w) {
 69                 dist[v] = dist[u]+w;
 70                 que.push(qnode(v, dist[v]));
 71                 path[v].u = u;
 72                 path[v].e = i;
 73             }
 74         }
 75     }
 76 }
 77 
 78 void init() {
 79     cnt = 0;
 80     memset(point, -1, sizeof(point));
 81 }
 82 
 83 int main() {
 84 #ifdef local
 85     if(freopen("/Users/Andrew/Desktop/data.txt", "r", stdin) == NULL) printf("can't open this file!
");
 86 #endif
 87     
 88     int n, m, k;
 89     scanf("%d%d%d", &n, &m, &k);
 90     init();
 91     for (int i = 0; i < m; ++i) {
 92         int u, v, w;
 93         scanf("%d%d%d", &u, &v, &w);
 94         AddEdge(u, v, w);
 95         AddEdge(v, u, w);
 96     }
 97     Dijkstra(n, 1);
 98     for (int i = 1; i <= n; ++i) {
 99         v1[path[i].u].push_back(i);
100         v2[path[i].u].push_back(path[i].e);
101     }
102     queue<int> q;
103     q.push(1);
104     int ans = 0;
105     int Ans[maxn];
106     while (q.size()) {
107         int tmp = q.front();
108         q.pop();
109         for (int j = 0; j < v1[tmp].size() && ans < k; ++j) {
110             q.push(v1[tmp][j]);
111             Ans[ans++] = v2[tmp][j]/2;
112         }
113     }
114     printf("%d
", ans);
115     for (int i = 0; i < ans; ++i) {
116         if (i)
117             printf(" %d", Ans[i]+1);
118         else printf("%d", Ans[i]+1);
119     }
120     printf("
");
121 #ifdef local
122     fclose(stdin);
123 #endif
124     return 0;
125 }

View Code