枣阳网站建设 枣阳山水数码,自己建网站备案,网站建设开发团队介绍,微信开放平台是干什么用的总体思路是用并查集来做。vec记录了目前断掉的路#xff0c;use记录了使用中的路。将断掉的路按照修复费用从小到大排序。
对每一个城市i失守进行讨论#xff0c;先根据use将其中两端城市进行union#xff0c;然后计算一下联通块个数。再按序找两个城市不在同一个联通块中的…总体思路是用并查集来做。vec记录了目前断掉的路use记录了使用中的路。将断掉的路按照修复费用从小到大排序。
对每一个城市i失守进行讨论先根据use将其中两端城市进行union然后计算一下联通块个数。再按序找两个城市不在同一个联通块中的vec将其union当联通块个数变为1的时候提前退出。当遍历完后若联通块数依然超过1则将修复费用设为INF。
代码如下
#include cstdio
#include vector
#include algorithm
#include utility
#include set
const int maxN 501;
const int INF 99999999;struct arc{int u;int v;int cost;arc(int _u, int _v, int _cost): u(_u), v(_v), cost(_cost){}
};int N, M, maxx, a, b, c, s;
int fa[maxN];
std::vectorarc vec;
std::vectorstd::pairint, int use;
std::vectorint curr;bool cmp(const arc m, const arc n){return m.cost n.cost;
}int findFather(int k){int x k;while(k ! fa[k]){k fa[k];}int t;while(x ! fa[x]){t fa[x];fa[x] k;x t;}return k;
}void Union(int m, int n){fa[findFather(m)] findFather(n);return;
}int main(){scanf(%d %d, N, M);for(int i 0; i M; i){scanf(%d %d %d %d, a, b, c, s);if(s 0){vec.push_back(arc(a, b, c));} else{use.push_back({a, b});}}sort(vec.begin(), vec.end(), cmp);maxx 0;for(int i 1; i N; i){for(int j 1; j N; j){fa[j] j;}for(int j 0; j use.size(); j){if(use[j].first ! i use[j].second ! i){Union(use[j].first, use[j].second);}}std::setint st;for(int j 1; j N; j){if(j ! i){st.insert(findFather(j));}}int sz st.size() - 1;if(sz 0){continue;}int tmp 0;int p 0;for(int j 0; j vec.size(); j){if(findFather(vec[j].u) ! findFather(vec[j].v) vec[j].u ! i vec[j].v ! i){tmp vec[j].cost;Union(vec[j].u, vec[j].v);p;}if(p sz){break;}}if(p sz){tmp INF;}if(tmp maxx){maxx tmp;curr.clear();curr.push_back(i);} else if(tmp maxx){curr.push_back(i);}}if(maxx 0){printf(0);return 0;}for(int i 0; i curr.size(); i){printf(%d%s, curr[i], i curr.size() - 1 ? \n : );}return 0;
}
题目如下
It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city.
Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 2 numbers N (≤500), and M, which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers: City1 City2 Cost Status where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.
Note: It is guaranteed that the whole country was connected before the war.
Output Specification:
For each test case, just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the connection if that city is conquered by the enemy.
In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space, but no extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.
Sample Input 1:
4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 1 0Sample Output 1:
1 2Sample Input 2:
4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 2 1Sample Output 2:
0
