http://acm.hdu.edu.cn/showproblem.php?pid=4424
【题目大意】
给你N个点和N-1条边的连通图，也就是说任意两点间的路径是唯一的。每条边有个权值，从一点到另一点的最大流量是路径中所有边中权值的最小值。要你找一个点，使得这点到剩下所有点的最大流量之和最大，求这个最大流量和。
【分析1：动态规划 】
假设现在有两个点的集合S1和S2，添加的一条边可以使得这两个集合连通起来，要求最大的流量之和，那么只有两种情况：1、选取的中心点在S1中；2、选取的中心点在S2中。设S中其最小权值的边为E，它连接S1、S2，假设中心点在S1，那么S2中所有的点要连接到中心点必然要通过E这条边过去，且这条边是短板；中心点在S2也类似，所以可以得到如下的DP方程：
DP[S]=max{DP[S1]+e.c*count[S2] , DP[S2]+e.c*count[S1] } (e.c为边的权值，count为集合中点的数量)
可以用搜索的方法来求对于每层枚举找到最小的边E，再递归下去，直到集合只含一个点，这是种逆向求解的想法，从整体到局部再反推回答案。
【分析2：并查集 & 贪心】
动态规划的方法虽然正确，复杂度也还算可以，但是复杂，涉及到集合的运算和从集合中遍历元素等等... 所以有种贪心的想法：既然每次都是取最小的边，那么随着递推下去，取的边构成的数列是递增有序的，那为什么不直接先把边排序好呢？既然在动态规划中涉及到集合的分裂，那为什么不反过来用集合的合并来求解？这两个是可以同时做到的。
所以可以得到以下做法: 把边从大到小排序，依次选取边的两点所在的集合来合并，并更新集合的元素个数和当前的最大和，用并查集就好了。这种方法其实是动态规划的逆向求解，但本质还是动态规划。
【代码】
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n;
long long sum[];
int mset[];
struct egde
{
int a,b,c;
void read(){scanf("%d%d%d",&a,&b,&c);}
bool operator<(const egde& t)const {return c>t.c;}
}data[];
int find(int x)
{
if (mset[x]<) return x;
return mset[x]=find(mset[x]);
}
void uion(int a,int b,int c)
{
int aa=find(a);
int bb=find(b);
long long sum1=sum[aa]+(long long)c*-mset[bb];
long long sum2=sum[bb]+(long long)c*-mset[aa];
if (sum2>sum1) {swap(aa,bb);swap(a,b);swap(sum1,sum2);}
mset[aa]+=mset[bb];
mset[bb]=aa;
sum[aa]=sum1;
}
int main()
{
while (~scanf("%d",&n))
{
memset(sum,,sizeof sum);
memset(mset,-,sizeof mset);
for (int i=;i<n-;++i) data[i].read();
sort(data,data+n-);
for (int i=;i<n-;++i)
uion(data[i].a,data[i].b,data[i].c);
printf("%I64d\n",sum[find()]);
}
}