zoj 3659 Conquer a New Region(并查集)

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4882

代码：

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

const int maxn = 200005;

struct Edge
{
    int u,v,w;
    Edge(int u=0,int v=0,int w=0): u(u), v(v), w(w) {}
    bool operator < (const Edge& rhs) const
    {
        return w > rhs.w;
    }
}edges[maxn];

int counts[maxn];
int pa[maxn];
long long cap[maxn];

int find(int x)
{
    return x == pa[x] ? x : pa[x] = find(pa[x]);
}

int main()
{
    //freopen("E:\acm\input.txt","r",stdin);
    int N;
    while(cin>>N)
    {
        for(int i=1; i<=N; i++)
        {
            counts[i] = 1;
            pa[i] = i;
            cap[i] = 0;
        }

        for(int i=1; i<N; i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            edges[i] = Edge(a,b,c);
        }
        sort(edges+1,edges+N);

        long long ans = 0;
        for(int i=1; i<N; i++)
        {
            long long w = edges[i].w;
            int u_fa = find(edges[i].u);
            int v_fa = find(edges[i].v);

            //下面目的是维护根到集合中所有的点cap值最大
            long long Lu = cap[u_fa] + w*counts[v_fa];
            long long Rv = cap[v_fa] + w*counts[u_fa];
            if(Lu > Rv)
            {
                pa[v_fa] = u_fa;
                cap[u_fa] = Lu;
                counts[u_fa] += counts[v_fa];
            }
            else
            {
                pa[u_fa] = v_fa;
                cap[v_fa] = Rv;
                counts[v_fa] += counts[u_fa];
            }
        }
        for(int i=1; i<=N; i++)
            ans = max(ans,cap[i]);
        cout<<ans<<"
";
    }
}