ZOJ 3659 & HDU 4424 Conquer a New Region (并查集)

这题要用到一点贪心的思想，因为一个点到另一个点的运载能力决定于其间的边的最小权值，所以先把线段按权值从大到小排个序，每次加的边都比以前小，然后合并集合时，比较 x = findset(a) 做根或 y = findset(b) 做根时，总权值的大小，x做根的总权值 ca = num[b]*w + cap[a] ，b同理。即b这个集合的点个数乘以新加的边的距离为新增的权值。然后合并。。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#define Mod 1000000007
using namespace std;
#define N 200010

int fa[N];
ll cap[N];
int num[N];
ll ans;

void makeset(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i] = i;
        num[i] = 1;
        cap[i] = 0;
    }
}

int findset(int x)
{
    if(x != fa[x])
    {
        fa[x] = findset(fa[x]);
    }
    return fa[x];
}

void unionset(int a,int b,int c)
{
    int x = findset(a);
    int y = findset(b);
    if(x == y)
        return;
    ll ca = (ll)num[y]*c + cap[x];  //一定要手动转化成long long 
    ll cb = (ll)num[x]*c + cap[y];
    if(ca >= cb)
    {
        fa[y] = x;
        num[x] += num[y];
        cap[x] = ca;
    }
    else
    {
        fa[x] = y;
        num[y] += num[x];
        cap[y] = cb;
    }
    ans = max(ans,max(ca,cb));
}

struct node
{
    int u,v,w;
}se[N];

int cmp(node a,node b)
{
    return a.w>b.w;
}

int main()
{
    int n,i;
    int a,b,c;
    while(scanf("%d",&n)!=EOF)
    {
        makeset(n);
        ans = -Mod;
        for(i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&se[i].u,&se[i].v,&se[i].w);
        }
        sort(se,se+n-1,cmp);
        for(i=0;i<n-1;i++)
            unionset(se[i].u,se[i].v,se[i].w);
        cout<<ans<<endl;
    }
    return 0;
}

要注意每个地方能转化成同一类型的尽量转化为同一类型，如强制转化为long long，以避免无谓的WA。