HDU 4424 Conquer a New Region 最大生成樹

HDU 4424 Conquer a New Region 最大生成樹

給你一顆樹 每條邊有一個權值 選擇一個點為中心 定義S值為中心到其他n-1個點的路徑上的最小邊權 求所有點S值的和

從大到小排序 每次合並2棵樹 設為A集合 B集合 設A集合的最大S值的和為sumA B集合為sumB

中心在A或者B現在加入A-B這條邊使得2個集合連通 因為A-B這條邊的權值小於等於AB集合裡面邊的權值 所以如果合並之後中心在A 那麼sumA = sumA+B集合的點數*A-B這條邊的權值 sumB = sumB+A集合的點數*A-B這條邊的權值 2者取大

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 200010;
int n;
int f[maxn], rank[maxn];
__int64 sum[maxn];

struct edge
{
	int u, v, w;
}e[maxn];
int find(int x)
{
	if(x != f[x])
		return f[x] = find(f[x]);
	return f[x];
}
bool cmp(edge a, edge b)
{
	return a.w > b.w;
}
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		for(int i = 0; i < n-1; i++)
			scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
		sort(e, e+n-1, cmp);
		for(int i = 0; i <= n; i++)
			f[i] = i, sum[i] = 0, rank[i] = 1;
		for(int i = 0; i < n-1; i++)
		{
			int x = find(e[i].u);
			int y = find(e[i].v);
			if(x != y)
			{
				if(sum[x]+(__int64)e[i].w*rank[y] > sum[y]+(__int64)e[i].w*rank[x])
				{
					f[y] = x;
					sum[x] = sum[x]+(__int64)e[i].w*rank[y];
					rank[x] += rank[y];
				}
				else
				{
					f[x] = y;
					sum[y] = sum[y]+(__int64)e[i].w*rank[x];
					rank[y] += rank[x];
				}
			}
		}
		int x = find(1);
		printf("%I64d\n", sum[x]);
	}
	return 0;
}