Educational Codeforces Round 54 (Rated for Div. 2) D Edge Deletion (SPFA + bfs)

题目大意：给定你一个包含n个点m条边的无向图，现在最多在图中保留k条边，问怎么删除多的边，使得图中良好的节点数最多，求出保留在图中的边的数量和编号。

　　良好的节点定义为：删除某条边后该点到点1的最短距离不变。

思路：先求出所有点到点1的最短距离，之后再bfs一遍，若遍历到某一节点时的距离等于该点到点1的最短距离就将该条边加进去，直到添加到k条边或者遍历结束。（虽然过了但是还是觉得有有的情况好像过不了，但是没想出来...可能数据还有点水..）

　　一开始INF值设小了WA了四次。。。 INF值设置1e15即可，因为边的权值很大所以上限需要很大。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<queue>

 #include<map>

 using namespace std;

 typedef long long LL;

 typedef pair<LL,LL> P;

 const int maxn = 3e5+;

 const LL INF = 1e18;

 vector<int>ans;

 int n, m, k;

 struct node{

     LL to,cost;

     node() {}

     node(LL a, LL b) :to(a), cost(b) {}

 };

 vector<node> e[maxn];

 LL vis[maxn], f[maxn], dis[maxn];

 map<P,LL>mp;

 void SPFA(int s)

 {

     for (int i = ; i < maxn; i++) {

         vis[i] = ; f[i] = ;

         dis[i] = INF;

     }

     dis[s] = ;

     vis[s] = ; f[s]++;

     queue<int>Q;

     Q.push(s);

     while (!Q.empty()) {

         int t = Q.front(); Q.pop();

         vis[t] = ;

         for (int i = ; i < e[t].size(); i++) {

             LL tmp = e[t][i].to;

             if (dis[tmp] > dis[t] + e[t][i].cost) {

                 dis[tmp] = dis[t] + e[t][i].cost;

                 if (!vis[tmp]) {

                     vis[tmp] = ;

                     Q.push(tmp);

                     if (++f[tmp] > n)return;

                 }

             }

         }

     }

     return;

 }

 void BFS(LL x)

 {

     ans.clear();

     queue<node>Q;

     memset(vis,,sizeof(vis));

     Q.push(node(x,));

     vis[x] = ;

     while(!Q.empty()&&ans.size()<k){

         node dep = Q.front();Q.pop();

         for(int i=;i<e[dep.to].size();i++){

             LL to = e[dep.to][i].to;

             if(ans.size()>n-&&ans.size()<k){

                 ans.push_back(mp[make_pair(dep.to,to)]);

                 continue;

             }

             if(ans.size()==k)return;

             if(vis[to])continue;

             if((dep.cost+e[dep.to][i].cost)>dis[to])continue;

             ans.push_back(mp[make_pair(dep.to,to)]);

             vis[to] = ;

             Q.push(node(to,dep.cost+e[dep.to][i].cost));

             if(ans.size()==k)return;

         }

     }

 }

 int main()

 {

     ios::sync_with_stdio(false);

     while (cin >> n >> m >> k) {

         mp.clear();

         for(int i=;i<=n;i++)e[i].clear();

         for (LL a, b, c, i = ; i <= m; i++) {

             cin >> a >> b >> c;

             e[a].push_back(node(b, c));

             e[b].push_back(node(a, c));

             mp[make_pair(a,b)] = i;

             mp[make_pair(b,a)] = i;

             // cout<<mp[make_pair(a,b)]<<endl;

         }

         if(k==){

             cout<<""<<endl;

             continue;

         }

         SPFA();

         BFS();

         cout<<ans.size()<<endl;

         for(int i=;i<ans.size()-;i++)

             cout<<ans[i]<<" ";

         cout<<ans[ans.size()-]<<endl;

     }

     return ;

 }

巴特西

Educational Codeforces Round 54 (Rated for Div. 2) D Edge Deletion (SPFA + bfs)

最新文章

热门文章