Acwing_346走廊泼水节【最小生成树应用: 最小完全图】_树要添加多少边得到完全图

题目描述:

给定一棵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
1
2
3
4
5
6
7
8

输出样例：

4
17
1
2

思路分析:

• 要扩充成完全图也就是在建树的过程中把每次新加入的连通块和当前连通块中每一对点两两相连，如果要最后完全图的权值和最小，也就是每一次连连通块的时候的边最小，每一次连连通块的边必须要满足大于原来树中把这两个连通块连起来的边的权值，因为如果小于，该树就不再是最小生成树了，等于的话，就不是唯一的最小生成树

AC代码:

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

using namespace std;

const int N = 6010;
int n; 
struct Edge {
	int a, b, w;
	bool operator<(const Edge&t)const {
		return w < t.w;
	}
}e[N];

int p[N],_size[N];

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

int main()
{

	int T;
	cin >> T;
	while (T--) 
	{
		int res = 0;
		cin >> n;
		for (int i = 0; i < n-1; i++) {
			int a, b, w;
			cin >> a >> b >> w;
			e[i] = { a,b,w };
		}
		sort(e, e + n-1);
		for (int i = 1; i <= n; i++) p[i] = i,_size[i]=1;
		for (int i = 0; i < n; i++) {
			int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
			if (a != b) {
				res += (_size[a] * _size[b] - 1)*(w + 1);
				_size[b] += _size[a];
				p[a] = b;
			}

		}
		cout << res << endl;
	}



	system("pause");
	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