走廊泼水节(最小生成树定理)⭐

题面

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

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

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

输入格式

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

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

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

输出格式

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

每个结果占一行。

数据范围

1≤N≤6000
1≤Z≤100

输入样例：

输出样例：

4
17

题解

这道题考的是最小生成树定理

定理
任意一颗最小生成树一定包含无向图中权值最小的边

证明(反证法)

假设G = (V, E)存在一颗最小生成树不包含权值最小边(x, y, z),
将(x, y, z)加入图中,则出现环, 最小生成树, 不能有环,
所以要从这个环中删去一条边(当然能树还是联通的),
这个环中任一条边都比(x, y, z)大, 故肯定留下这条边, 故这颗生成树不是最小生成树

推论⭐

给定一张无向图G(V,E), n = |V|, m = |E|, 从E中选k< n - 1条边构成G的森林
若在从m = k条边中选(n - 1 - k)构成G的生成树,并且边权值最小,
则给生成树必定包含 m - k条边中连接最小生成树的边来连接森林的两棵树

故这道题就是不断选链接森林且是最小生成树的边

所以存在森林, 然后用体中的一条边(x, y, z)将 x节点和 y节点所在的树链接

因为要生成完全图,则着两棵树中的所有节点添加边权都要为 z + 1

不然如果小于等于z, 这条新添加的边链接了x和y所在的树, 且边权值最小, 则必定为最小生成树的边(和题意矛盾)

所以就是一边连边, 一边添加 z + 1边

实现细节见代码

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;

const int maxn = 6005;

struct rec { int x, y, z; } e[maxn];

bool operator <(rec& a, rec& b)
{
    return a.z < b.z;
}


int _, n, fa[maxn], s[maxn];

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

void unit(int x, int y)
{
    x = find(x), y = find(y);
    fa[y] = x, s[x] += s[y];
}

int main ()
{
    for (cin >> _; _; --_)
    {
        cin >> n; fa[n] = n, s[n] = 1;
        rep (i, 1, n - 1) 
            cin >> e[i].x >> e[i].y >> e[i].z, fa[i] = i, s[i] = 1;
        sort(e + 1, e + n);
        
        ll ans = 0;
        rep (i, 1, n - 1)
        {
            int x = find(e[i].x), y = find(e[i].y);
            if (x == y) continue;
            ans += (ll)(e[i].z + 1) * (s[x] * s[y] - 1);
            unit(x, y);
        }
        cout << ans << '
';
    }
    return 0;
}