学步园

初看这道题感觉无法下手啊。。。

但是我是不会就这么屈服的！！我仔细想了想，既然图的生成树是唯一的

那么如果我们对最后图用kruskal进行生成树的构造，每一次都不会有相同长度的边出现

kruskal的算法，是每一次连通两个连通块，且边权尽量小，我们假设这个边权是l

那么 这两个连通块之间的其他连线肯定>l   !!!

那么每次我们连通两个连通块时，就可以得到这两个连通块其他线的最小长度

主题流程就出来了：

1.读取所有边

2.排序

3.加入这些边，每次加入一条边，就得到两端点所在连通块间的其他线的长度，加上这些长度

4.最后输出ans

实现就是基于并查集（要统计每个连通块的元素个数）的算法。。。

现在想一下为什么要模拟kruskal而不是prim

满足kruskal的，一定满足prim，满足prim的不一定满足kruskal！

也就是说必须按kruskal的来，再说了，，prim咱也模仿不出。。。

这道题还有一点坑的地方是：仅仅ans是64位是会WA掉的

我把所有变量改long lont 后才AC。。。。。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAX 20001
typedef long long LL;	
struct node
{
	LL a;
	LL b;
	LL l;
}line[MAX];
bool operator<(node a,node b)
{
	return a.l < b.l;
}
LL n;
LL mot[MAX],num[MAX],ans;
LL find(LL x)
{
	if ( x != mot[x] )
	{
		mot[x] = find(mot[x]);
	}
	return mot[x];
}
void merge(LL a,LL b,LL l)
{
	a = find(a);
	b = find(b);
	ans += (num[a] * num[b] -1) * (l+1);
	mot[b] = a;
	num[a] += num[b];
}
void init()
{
	cin>>n;
	for (LL i = 1; i < n; i++)
	{
		scanf("%I64d%I64d%I64d",&line[i].a,&line[i].b,&line[i].l);
	}
}
void work()
{
	for (LL i = 1; i <= n; i++)
	{
		mot[i] = i;
		num[i] = 1;
	}
	sort(line+1,line+n);
	for (LL i = 1; i < n; i++)
	{
		ans += line[i].l;
		merge(line[i].a,line[i].b,line[i].l);
	}
}
void print()
{
	cout<<ans;
}
int main()
{
	init();
	work();
	print();
	return 0;
}