Kruskal算法 走廊泼水节 CH6201_给定一棵n个节点的树,要求增加若干条边,把这棵树扩充为完全图,并满足图的唯一最小

问题描述
给定一棵N个节点的树，要求增加若干条边，把这棵树扩充为完全图，
并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。
注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

输入格式
第一行包含整数t，表示共有t组测试数据。

对于每组测试数据，第一行包含整数N。

接下来N-1行，每行三个整数X,Y,Z，表示X节点与Y节点之间存在一条边，长度为Z。

输出格式
每组数据输出一个整数，表示权值总和最小值。

每个结果占一行。

数据范围
1 ≤ N ≤ 6000
1 ≤ Z ≤ 100

输入样例：
2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5 
输出样例：
4
17 
1
2
3
4
5
6
7
8
9
10
11
12

思路
将每条边安从小到大排序，将这些边按照Kruskal算法做最小生成树的操作，保证每个集合内的点都是完全图，所以在合并集合的同时计算连接所有的点所需要的边权之和，连接两个集合的边数为两个集合的点数相乘减去一，边权为当前的最小生成树的这个边的权值加一（满足整数要求）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;
const int N = 6010;

struct node
{
	int x, y, z;
	bool operator<(const node &a) const
	{
		return z < a.z;
	}
} e[N];

int f[N], s[N];
ll ans;
int n;

void init()
{
	for (int i = 0; i <= N - 1; i++)
	{
		s[i] = 1;
		f[i] = i;
	}
}

int find(int x)
{
	if (f[x] == x)
		return x;
	return f[x] = find(f[x]);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		init();
		ans = 0;
		scanf("%d", &n);

		for (int i = 0; i < n - 1; i++)
		{
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			e[i] = {a, b, c};
		}

		sort(e, e + n - 1);

		for (int i = 0; i < n - 1; i++)
		{
			int x = e[i].x;
			int y = e[i].y;
			int z = e[i].z;
			x = find(x);
			y = find(y);
			if (x != y)
			{
				ans += (1ll * z + 1) * (s[x] * s[y] - 1);
				f[x] = f[y];
				s[y] += s[x];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77