Acwing 346.走廊泼水节（最小生成树）

Acwing 346.走廊泼水节

题意

给定一棵 N 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

思路

考虑在求最小生成树的过程中加边，因为要加成完全图，所以每次合并两个连通块时，左边连通块的点到右边连通块的点都应该加上一条边，那么加边的权值应该是多少呢？

不妨假设以下三种情况：

设 w 为最小生成树当前的边

1. 新边 < w
2. 新边 = w
3. 新边 > w

因为求最小生成树的过程中每次判断当前权值最小的边是否可以加入到最小生成树中，如果有边比 w 小，那么一定不会选 w 这条边，那么最小生成树就会改变。所以第一种情况不符合要求。

对于情况二，因为权值都一样，所以在符合最小生成树构造过程的前提下，可以选择任意一条边，虽然最小生成树的权值不会改变，但是不一定是原来的那颗树，所以第二种情况也不符合要求。

对于情况三，因为每次加的新边都比 w 要大，所以最小生成树的权值不会改变，并且一定是原来那棵树。因为要求新加边的权值总和最小值，所以设置新边的权值为 $w+1$ 即可。

代码

// Author：zzqwtcc
// Problem: 走廊泼水节
// Contest: AcWing
// Time：2021-10-20 21:01:55
// URL: https://www.acwing.com/problem/content/348/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T,typename S>inline void debug(S s,T t){cerr << s << " " << t << endl;}
template<typename T>inline void debug(T t){cerr << t << endl;}
// template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }

const int N = 6010;
int n;
int f[N];
int siz[N];

struct Edge{
	int u,v,w;
	
	bool operator<(const Edge & e)const {
		return this->w < e.w;
	}
}edge[N];

void init(){
	for(int i = 1; i <= n;++i)f[i] = i,siz[i] = 1;
}

int Find(int x){
	return x == f[x] ? f[x] : f[x] = Find(f[x]);
}

void merge(int a,int b){
	int fa = Find(a);
	int fb = Find(b);
	f[fb] = fa;
	siz[fa] += siz[fb];
}

void solve() {
    cin >> n;
    init();
    for(int i = 1; i <= n - 1;++i){
    	cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    
    sort(edge + 1,edge + 1 + n - 1);
    
    LL res = 0;
    for(int i = 1; i <= n - 1;++i){
    	int u = edge[i].u, v = edge[i].v, w = edge[i].w;
    	if(Find(u) == Find(v))continue;
    	else{
			 res += (LL)(w + 1) * (siz[Find(u)] * siz[Find(v)] - 1);
    		merge(u,v);
    	}
    }
    
    cout << res << endl;
}

signed main() {

    int _; cin >> _;
    while (_--)
        solve();

    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
78
79
80
81
82
83
84
85
86
87