走廊泼水节

Kruscal扩展 由结果更新 T4 最小生成树 346. 走廊泼水节 - AcWing题库

题目

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

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

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

输入格式

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

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

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

输出格式

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

每个结果占一行。

数据范围

$1\le N\le 6000$
$1\le Z\le 100$

输入样例：

2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5 

输出样例：

4
17 

思路

一个无向图, 给n-1条边, 求用这n-1条边再加上一些边使其构成完全图, 且该图的最小生成树仍是加边之前的那个, 不能有多个最小生成树。

首先考虑怎么通过这n-1条边构成完全图, 且还要利于保留最小生成树, 正如设计密码一题, 其用正解来更新其他状态的思想在这里也体现了出来。

采用kruscal算法来对n-1条边求最小生成树, 再加完一条边A后, 将两个即将相连的集合加一些边构成完全图, 要加的边权值必须满足刚好大于原本的边A。若相等则会出现不唯一的最小生成树, 若小于则原本的最小生成树失效。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 6e3 + 10;
int f[N], Size[N];
struct Edge {
    int a, b, c;
    bool operator < (const Edge &W) const{
        return c < W.c;
    }
}e[N];
int n;
 
int find(int x) {return f[x] == x ? f[x] : f[x] = find(f[x]);}
 
int main()
{
    int t ;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++) f[i] = i, Size[i] = 1;
        for(int i = 0; i < n - 1; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            e[i] = {a,b,c};
        }
        sort(e, e + n - 1);
        int res = 0;
        for(int i = 0; i < n-1; i++)
        {
            int a = find(e[i].a), b = find(e[i].b), c = e[i].c;
            if(a != b)
            {
                res += (Size[a] * Size[b] - 1) * (c + 1);
                f[b] = a;
                Size[a] += Size[b];
            }
        }
        cout  << res << endl;
    }
    
    return 0;
}