【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
输出样例：
4
17

思路：

首先，题目给了n-1个结点，那么初始的树肯定就是唯一一颗，而且是最小生成树（没有多余边嘛）。现在我们要加边进来，使得加进来的边不影响我们最小生成树边的选择，要求这时候的加进来的边的总和最小。
回想Kruskal算法的步骤。存边排序，枚举边，若边的两点不在同一颗树内，就合并，否则不合并。那么，要加进来新的边又要尽可能小，就想尽可能地把这条边排在前面选，而且这条边两端点是同一个集合里面的。如图：红色代表原来的题给n-1条边，蓝色的是要加进图但是不能选入最小生成树的边（按边长排序）

那么，问题就变得简单了，我当前加了m条边了，形成了一颗m个结点的树，这时候我就可以把这m个结点两两连接构成边，边的长度就是当前选的这条边边长（目前最大的边）+1。因为这时候这些边就是相当于图上蓝色的边，尽可能的小且不影响到原来的树的选择。因为这时候这m个结点已经被选入树中了。所以，如下图，两条边要合并时，新构成的边就是num[a]*num[b]-1 。 （num[]表示各自根节点所含节点数量）
如图ab结点相连时，新构成的边就是2x3-1（左边结点全部连到右边减去重复的ab一条）。然后答案就是每次新构成边的数量乘上当前边长。累加即可

AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 6e3+2;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

ll n,m;
ll ans;
ll fa[maxn];
ll num[maxn];

typedef struct Edge
{
    ll x;
    ll y;
    ll dis;
}E;

E a[maxn];

bool cmp(E a, E b)
{
    return a.dis < b.dis;
}

void init()
{
    rep(i,1,n) fa[i] = i,num[i]=1;
    ans = 0;
}

ll get(ll x)
{
    if(x==fa[x]) return x;
    return fa[x] = get(fa[x]);
}

void merge(ll x, ll y,ll pos)
{
    ll a1 = get(x);
    ll b1 = get(y);
    if(a1!=b1)
    {
        fa[b1] = a1;
        ll dis = a[pos].dis;
        ans += (num[b1]*num[a1]-1)*(dis+1);
        num[a1] += num[b1];
    }
}


int main()
{
    int kase;
    cin>>kase;
    while(kase--)
    {
        cin>>n;
        init();
        rep(i,1,n-1) cin>>a[i].x>>a[i].y>>a[i].dis;
        sort(a+1,a+n,cmp);
        rep(i,1LL,n-1)
        {
            ll x = a[i].x;
            ll y = a[i].y;
            merge(x,y,i);
        }
        cout<<ans<<endl;
    }
    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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109