libreoj 10067 「一本通 3.1 练习 2」构造完全图 题解

发表于 | 阅读次数：
本文字数： 792 字 | 阅读时长 ≈ 4 分钟

题意简述

给定一个树 $T$ ，求一个完全图 $G$ 使得 $T$ 是 $G$ 的最小生成树，并且 $G$ 的边权和最小。求出这个最小的边权和。$T$ 的点数 $n\le 10^5$，每个边权 $w\le 10^5​$

思路

我们把 $T​$ 中的边权排一下序，反向推一下 Kruskal 算法的步骤。

我们每次考虑到第 $i​$ 条边 $(u,v,w)​$，假设这之前的 $i-1​$ 条边已经构造好了若干个都是完全图的联通块，并且 $T​$ 中的前 $i-1​$ 条边就是这些联通块的生成树（也就是保证了 Kruskal 算法前 $i-1​$ 步都选的是 $T​$ 中的边）。

在连上 $(u,v,w)$ 之前，$(u,v)$ 应该分在两个联通块里。我们把 $(u,v,w)$ 连起来之后，对于两个联通块里除了 $(u,v)$ 以外的所有点对，都连一条权为 $w+1$ 的边。这样，显然在 Kruskal 算法的第 $i$ 步中，选的是第 $i$ 条边（因为现在只剩下两个联通块连接，除了 $(u,v,w)$ 之外所有的边权都 $\ge w$，肯定得选 $(u,v,w)$）

所以我们把 $T$ 中的边按边权排序，并查集合并的时候记录一下联通块大小。然后 $(u,v,w)$ 这条边的贡献就是 $(cnt[u]\times cnt[v]-1)\times (w+1)​$

代码

点击
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
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 155555
	#define int long long 
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	int I()
	{
	    int x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    return (x=(f==1)?x:-x);
	}
	void Rd(int cnt,...)
	{
	    va_list args; va_start(args,cnt);
	    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
	    va_end(args);
	}
	class DSU
	{
	public:
		int Fa[N],Cnt[N];
		void Init(){F(i,0,N-1) Fa[i]=i,Cnt[i]=1;}
		int  Find(int u){return u==Fa[u]?u:Fa[u]=Find(Fa[u]);}
		bool Merge(int u,int v)
		{
			int au=Find(u),av=Find(v); if (au==av) return false;
			if (Cnt[au]<Cnt[av]) Cnt[av]+=Cnt[au],Fa[au]=av;
			else 				 Cnt[au]+=Cnt[av],Fa[av]=au;
			return true;
		}
	}D;
	struct node{int u,v,w;}e[N]; bool operator<(node a,node b){return a.w<b.w;}
	int n;
	void Input()
	{
		n=I();
		F(i,1,n-1) e[i]=(node){I(),I(),I()};
	}

	void Soviet()
	{
		int ans=0; F(i,1,n-1) ans+=e[i].w; // 初始答案为所有边的边权和，这个显然
		sort(e+1,e+n);
		D.Init();
		F(i,1,n-1)
		{
			int u=e[i].u,v=e[i].v; int au=D.Find(u),av=D.Find(v);
			ans+=(D.Cnt[au]*D.Cnt[av]-1)*(e[i].w+1);
			D.Merge(u,v);
		}
		printf("%lld\n",ans);
	}

	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
	#undef int //long long
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w