TYVJ 1391 走廊泼水节【生成树】

链接太长放不下

---

大意

给定一棵$N$个节点的树，要求增加若干条边，把这棵树扩充为完全图，并完全图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少。
数据范围：$N\le 6000$，原有的边权均为非负整数

---

思路

首先题目要求完全图的唯一最小生成树仍然是这棵树，所以对于对两个点集合$x$，$y$之间的连边必须大于原长度，而又要求最小，所以自然是权值+1

那么我们对于一条边$(x,y,w)$，设$S_x$表示$x$所在的点集，$S_y$表示$y$所在的点集，而$S_x$与$S_y$之间必定会添加$|S_x|+|S_y|-1$条边，而每条边的长度都为$w+1$，如图

作图网页ProcessOn

---

代码

#include<cctype>
#include<cstdio>
#include<algorithm>
using namespace std;int n,f[6010],s[6010],T;
long long ans;
inline char Getchar()
{
    static char buf[100000],*p1=buf+100000,*pend=buf+100000;
    if(p1==pend)
	{
        p1=buf; pend=buf+fread(buf,1,100000,stdin);
        if (pend==p1) return -1;
    }
    return *p1++;
}
inline int read()
{
	char c;int d=1,f=0;
	while(c=Getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=Getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
inline void write(register long long x)
{
	if(x<0)write(45),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
	return;
}//以上为输入输出优化
struct node{int x,y,w;}edge[6010];
inline bool cmp(node x,node y){return x.w<y.w;}//排序
inline int find(register int x){return x==f[x]?x:f[x]=find(f[x]);}//判断所处集合
signed main()
{
	T=read();
	while(T--)
	{
		n=read();
		for(register int i=1;i<n;i++)edge[i]=(node){read(),read(),read()};
		sort(edge+1,edge+n,cmp);
		for(register int i=1;i<=n;i++) f[i]=i,s[i]=1;
		ans=0;
		for(register int i=1;i<n;i++)
		{
			int fx=find(edge[i].x),fy=find(edge[i].y);
			if(fx==fy) continue;
			ans+=(long long)(edge[i].w+1)*(s[fx]*s[fy]-1);
			f[fx]=fy;s[fy]+=s[fx];//集合被合并
		}
		write(ans);putchar(10);
	}
}
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