算法：ZOJ 3659 Conquer a New Region（并查集）

算法：ZOJ 3659 Conquer a New Region（并查集）2014-01-10 csdn shuangde800【题目大意】

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