HDU 4424 Conquer a New Region 並查集，hdu4424

HDU 4424 Conquer a New Region 並查集，hdu4424

題意：給出n個點和n-1條邊，a到b的最大承載量為a和b之間承載量的最小值。以某一點為中心，求承載量之和的最大值。

由於a和b之間的承載量為它們之間承載量的最小值，所以先以兩點之間的承載量從大到小排序。每次合並時有A，B兩個集合，他們之間的承載量(cost)為當前最小，如果B合並到A，則A的總承載量為A之前的總承載量加上A，B之間的承載量成衣集合B中點的個數，即 cost[A]=cost[A]+num[B]*cost.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int inf=1000000000;
const int maxn=200005;
int f[maxn];
ll num[maxn],cost[maxn];

struct Branch
{
    int a;
    int b;
    ll cost;
}bra[maxn];
bool cmp(Branch a,Branch b)
{
    return a.cost>b.cost;
}
int Find(int x)
{
    if(x!=f[x])
        f[x]=Find(f[x]);
    return f[x];
}
ll Function(int n)
{
    for(int i=0;i<n-1;i++)
    {
        int a=Find(bra[i].a);
        int b=Find(bra[i].b);
        if(cost[a]+num[b]*bra[i].cost>=cost[b]+num[a]*bra[i].cost)
        {
            f[b]=a;
            cost[a]+=num[b]*bra[i].cost;
            num[a]+=num[b];
        }
        else
        {
            f[a]=b;
            cost[b]+=num[a]*bra[i].cost;
            num[b]+=num[a];
        }
    }
    return cost[Find(1)];
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=n;i++)
        {
            f[i]=i;
            num[i]=1;
        }
        memset(cost,0,sizeof(cost));
        for(int i=0;i<n-1;i++)
            scanf("%d%d%I64d",&bra[i].a,&bra[i].b,&bra[i].cost);
        sort(bra,bra+n-1,cmp);
        printf("%I64d\n",Function(n));
    }
    return 0;
}