算法：ZOJ 3659 Conquer a New Region(并查集)

【题目大意】

有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;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， const
， zoj
， 一个
， 城市
， 并查集
总和
new region参数、并查集、带权并查集、可持久化并查集、并查集 路径压缩，以便于您获取更多的相关知识。