本文共 1142 字，大约阅读时间需要 3 分钟。
【题目大意】
有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 #include #include #include #include #include #include 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 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://zpzni.baihongyu.com/