hdu 4424 Conquer a New Region

贪心+并查集。题目要求所有点到最一点经过的最小边之和最大。则有，对于两个集合A，B，也就是原树两颗子树，加上一条边使他们连通，有两种连接方案：1、使用A集合中的点作为center，则B集合中的点到center必经过新加入的边。1、使用B集合的点作为center，同理。这样的话我们就想到使新加入的边作为当前所有边的最小边，这样的话就容易计算和比较多了，于是问题就迎刃而解了：先加大边，然后并查集求值。

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<vector>  
#include<cstdio>  
#include<cmath>  
#include<set>  
#define LL long long  
#define CLR(a, b) memset(a, b, sizeof(a))  
using namespace std;  
  
  
const int N = 222222;  
const int MOD = 1e9 + 7;  
int fa[N], hav[N];LL val[N];  
  
struct Edge  
{  
    int u, v;LL c;  
    bool operator < (const Edge& rhs) const  
    {  
        return c > rhs.c;  
    }  
}E[N];  
  
int find(int x)  
{  
    return fa[x] != x ? fa[x] = find(fa[x]) : x;  
}  
  
int main()  
{  
    int u, v, i, j, n;LL ans;  
    while(scanf("%d", &n) != EOF)  
    {  
        for(i = 0; i < n - 1; i ++)  
        {  
            scanf("%d%d%I64d", &E[i].u, &E[i].v, &E[i].c);  
            fa[i + 1] = i + 1;  
            hav[i + 1] = 1;  
        }  
        hav[n] = 1;fa[n] = n;  
        CLR(val, 0);  
        sort(E, E + n - 1);  
        for(i = 0; i < n - 1; i ++)  
        {  
            u = find(E[i].u);  
            v = find(E[i].v);  
            if(val[u] + hav[v] * E[i].c > val[v] + hav[u] * E[i].c)  
            {  
                val[u] += hav[v] * E[i].c;  
                hav[u] += hav[v];  
                fa[v] = u;  
            }  
            else  
            {  
                val[v] += hav[u] * E[i].c;  
                hav[v] += hav[u];  
                fa[u] = v;  
            }  
        }  
        printf("%I64d\n", val[find(1)]);  
    }  
}

补充：软件开发 , C++ ,