ZOJ 3659 Conquer a New Region(并查集)

题目链接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3659

【题目大意】

有N个城市，N-1条路把这些城市连起来（刚好是一个树）。相邻的两个城市有一个运输容量C(i, j)，而城市x到城市y的那条路的运输能力S取决与这条路上所经过的所有路中最小的那个容量。 以那一个城市为中心，到其他N-1个城市的运输能力总和最大？

【思路】

用神奇的并查集，把路按照权值从大到小排序，然后用类似Kruskal的方法不断的加入边。 对于要加入的一条路，这条路连接这城市x和y，x所在的集合为A， y所在的集合为B， 可以确定A,B集合内的所有路都比当前这条路的权值大。如果让集合B加入集合A，就是让中心城市位于集合A，那么可以确定这两个集合合并之后的总权值为: A的权值总和+B的数量*当前这条路的权值。同样算出让集合B加入集合A的情况，取两者合并后权值大的进行合并。

【代码】

#include<iostream> 
#include<cstdio>
#include<cstring>
#include<utility>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 200010;
const double eps = 1e-7;
int n;
int f[MAXN], cnt[MAXN];
int64 sum[MAXN];

struct Edge{
    int a, b, w;
    bool operator<(const Edge&rhs) const{
        return w > rhs.w;
    }
}arr[MAXN];

void init(){
    for(int i=0; i<=n; ++i){
        f[i] = i;
        cnt[i] = 1;
        sum[i] = 0;
    }
}

int find(int x){
    int i, j=x;
    while(j != f[j]) j = f[j];
    while(x != j){ i=f[x]; f[x]=j; x=i; }
    return j;
}

int main(){

    while(~scanf("%d", &n)){
       
        for(int i=0; i<n-1; ++i)
            scanf("%d%d%d", &arr[i].a, &arr[i].b, &arr[i].w);

        init();
        sort(arr, arr+n-1);

        int64 ans = 0;
        for(int i=0; i<n-1; ++i){
            int ra=find(arr[i].a), rb=find(arr[i].b);
            int64 toa = (int64)cnt[rb]*arr[i].w + sum[ra];
            int64 tob = (int64)cnt[ra]*arr[i].w + sum[rb];
            if(toa > tob){
                f[rb] = ra;
                sum[ra] = toa;
                cnt[ra] += cnt[rb];
            }else{
                f[ra] = rb;
                sum[rb] = tob;
                cnt[rb] += cnt[ra];
            }
            ans = max(ans, max(toa, tob));
        }
        cout << ans << endl;
    }
    return 0;
}