HDU 4424 Conquer a New Region(分治并查集最大生成树)

Conquer a New Region

Time Limit: 8000/4000 MS(Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2421 Accepted Submission(s): 872

Problem Description

The wheel of the history rolling forward, our kingconquered a new region in a distant continent.
There are N towns (numbered from 1 to N) in this region connected by severalroads. It's confirmed that there is exact one route between any two towns.Traffic is important while controlled colonies are far away from the localcountry. We define the capacity C(i, j) of a road indicating it is allowed totransport at most C(i, j) goods between town i and town j if there is a roadbetween them. And for a route between i and j, we define a value S(i, j)indicating the maximum traffic capacity between i and j which is equal to theminimum capacity of the roads on the route.
Our king wants to select a center town to restore his war-resources in whichthe total traffic capacities from the center to the other N - 1 towns ismaximized. Now, you, the best programmer in the kingdom, should help our kingto select this center.

Input

There are multiple test cases.
The first line of each case contains an integer N. (1 <= N <= 200,000)
The next N - 1 lines each contains three integers a, b, c indicating there is aroad between town a and town b whose capacity is c. (1 <= a, b <= N, 1<= c <= 100,000)

Output

For each test case, output an integer indicating thetotal traffic capacity of the chosen center town.

Sample Input

1 2 2

2 4 1

2 3 1

1 2 1

2 4 1

2 3 1

Sample Output

Source

2012 Asia ChangChun Regional Contest

Recommend

zhuyuanchen520

2012年长春现场赛E题，关于图论

题目意思：

现在有若干个城镇，联通，形成一个生成树。城市与城市之间有所谓的容量，现在国王想要找到一个城镇，这个城镇到其他各个城镇的容量和最大（注意，两个城镇之间的容量和为这条路径上路径容量最小的权值）

例如说从U到V有一条路径，要经过三条边，容量分别为1->4->6

那么从U到V的容量就为这三条边中最小的那个，即是1。

现在国王想要在所有城镇中找到一个城镇，使得到其他各个城镇的容量和最大。

解题思路：

题目给的是一个树，已经联通。

先讲下朴素方法：我们可以枚举每个点，然后求路径，然后求每条路径上的最小值，再求权值和。最后找到最大的那个。

这种方法必然超时

我们明确一点，这有点像木板效应。一条路径上的权值取决于这条路径上权值最小的边。我们将边排序以后，从大到小排序。然后依次枚举每条边。

当一条边将图划分为两个集合时，这条边是关键边。我们要找的答案不在左边的集合，就在右边的集合，到底在哪一个？我们判断一下

假设答案在左边，那么最后的权值和为左边的权值和+右边集合的点数*关键边

假设答案在右边，那么最后的权值和为右边的权值和+左边集合的点数*关键边

（那第一个举例子，假设答案在左边的集合，那么答案到右边的集合上的点一定要经过关键边，这个关键边的权值又是最小的，小于左右两个集合中所有的边。所以左边的答案到右边集合的点的权值和关键边的权值）

这样简单判断下，就可以不断划分下去。将问题越分越小。有分治的思想在里面

最后能够把所有点划分到一个集合，这个集合中的根节点就是答案。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define Maxn 200010
using namespace std;

int n;
int fa[Maxn],num[Maxn];
long long sum[Maxn];
struct node
{
	int u,v;
	long long  cost;
}edge[Maxn];
bool cmp(struct node a,struct node b){return a.cost>b.cost;}
int getfa(int x)
{
	if(x==fa[x])
		return x;
	return fa[x]=getfa(fa[x]);
}
void init()
{
	memset(sum,0,sizeof sum);

	for(int i=1;i<=n;i++)
	{
		num[i]=1;
		fa[i]=i;
	}
}
int main()
{
	while(scanf("%lld",&n)!=EOF)
	{
		int i,j,a,b;
		int u,v,t1,t2;
		long long c,tmp1,tmp2;
		init();
		for(i=1;i<n;i++)
		{
			scanf("%d%d%lld",&a,&b,&c);
			edge[i].u=a; edge[i].v=b; edge[i].cost=c;
		}
		sort(edge+1,edge+n,cmp);
		for(i=1;i<n;i++)
		{
			t1=getfa(edge[i].u);
			t2=getfa(edge[i].v);
			tmp1=sum[t1]+num[t2]*edge[i].cost;
			tmp2=sum[t2]+num[t1]*edge[i].cost;
			if(tmp1>tmp2)//答案在t1树上
			{
				fa[t2]=t1;
				num[t1]+=num[t2];
				sum[t1]=tmp1;
			}
			else
			{
				fa[t1]=t2;
				num[t2]+=num[t1];
				sum[t2]=tmp2;
			}
		printf("%lld\n",sum[ getfa(1) ]);
	}
}