首页 > > 程序设计 > C/C++ >

HDU 4424 Conquer a New Region 并查集

2018-06-17 23:53:55来源：未知阅读 ()

题意：给出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;
}