【PAT顶】1001 Battle Over Cities - Hard Version (35 分) Kruskal求最小生成树

problem

1001 Battle Over Cities - Hard Version (35 分)
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 0
Sample Output 1:
1 2
Sample Input 2:
4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 2 1
Sample Output 2:
0

• n个城市，m条边，有些边废弃有些没有，废弃的边有一个修复代价。
• 现在如果去掉某个城市，要让剩余的城市连通，就需要维修一些边，维修代价称为这个点的重要性。
• 求重要性最大的城市（多个就按顺序输出），如果都不需要维修输出0，如果无法连通那么就是最大代价即正无穷。

solution

• 枚举每个点，假设去掉他，剩下的点跑Kruskal求最小生成树。
• 开个全局变量维护一下最小生成树最大的值就是答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;

int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}

struct edge{ int u, v, w, o;}e[maxn];
bool cmp(edge a, edge b){return a.o==b.o?a.w<b.w:a.o>b.o; }

int main(){
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= m; i++)
        cin>>e[i].u>>e[i].v>>e[i].w>>e[i].o;
    sort(e+1,e+m+1,cmp);        //不用修<维修代价小<代价大
    int ans = 0;
    vector<int>vc;
    for(int i = 1; i <= n; i++){//去掉i点
        init(n);
        int res = 0;  //Kruskal
        for(int j = 1; j <= m; j++){
            int x = find(e[j].u), y = find(e[j].v);
            if(x!=i && y!=i && x != y){
                res += e[j].o == 0 ? e[j].w : 0;
                merge(x,y);
            }
        }
        if(count(n)>2)res = 1e9+10; 
        if(res == ans)vc.push_back(i);
        else if(res > ans){
            vc.clear();
            vc.push_back(i);
            ans = res;
        }
    }
    if(ans==0)cout<<"0\n";
    else{
        for(int i = 0; i < vc.size(); i++){
            if(i!=0)cout<<" ";
            cout<<vc[i];
        }
    }
    return 0;
}