题意理解
这道题目说的很清楚,就是让我们将一个最小生成树的图,添加一些边,使得这张图成为一个完全图.
但是我们这张图的最小生成树,必须还是原来那张图的最小生成树.
也就是说两张图的最小生成树表示是一模一样的.
算法解析
根据上面的信息,我们不难发现这道题目和最小生成树算法联系紧密,那么现在我们的主要问题就在于如何去构造最小生成树.
我们可以考虑最小生成树算法中的Kruskal算法.
首先将所有的边按照从小到大的顺序排序.
此时我们保证了是最小生成树的完美生成法则.
对于每一条边(x,y,w)(x,y,w)而言,他们之间有某种关系.
假如说xx和yy不在同一个连通块(集合)之中,也就是他们之间没有边相连
那么我们相连之后,现在这两个点,各自所在的连通块(集合),都拥有了一个最短边,也就是(x,y,w)(x,y,w).
最小生成树是已经确定了,但是对于这原来两个连通块的其他点怎么办?
首先我们设Sx表示为x之前所在的连通块 那么Sy表示为y之前所在的连通块.
.
因为我们不能破坏这个最小生成树,所以我们这原来的两个连通块中的点就必须有如下性质.
假如说点A属于Sx这个集合之中 点B属于Sy这个集合之中.
那么点AA与点BB之间的距离,必须要大于之前的ww,否则就会破坏之前的最小生成树
所以说(A,B)之间的距离最小为w+1
假如说我们知道
Sx有p个元素,然后Sy有q个元素.
那么将
Sx与Sy连通块的所有点相连.
显然这个两个连通块会增加.
p×q−1条边
然后每一条边的最小长度为
w+1
所以我们会得出
(w+1)×(p∗q−1)为两个连通块成为完全图的最小代价
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct rec { int x, y, z; } edge[6010];
int fa[6010], s[6010], n, T;
long long ans;
bool operator <(rec a, rec b) {
return a.z < b.z;
}
int get(int x) {
if (x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
int main() {
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i < n; i++)
scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);
sort(edge + 1, edge + n);
for (int i = 1; i <= n; i++)
fa[i] = i, s[i] = 1;
ans = 0;
for (int i = 1; i < n; i++) {
int x = get(edge[i].x);
int y = get(edge[i].y);
if (x == y) continue;
ans += (long long)(edge[i].z + 1) * (s[x] * s[y] - 1);
fa[x] = y;
s[y] += s[x];
}
cout << ans << endl;
}
}