最小生成树

模板题：【模板】最小生成树

求最小生成树的边权和。

Prim

这似乎是我最早学的最小生成树算法。也是忘的最早的

首先注意到，由 \(n\) 个节点和 $ n-1 $ 条边构成的 连通图 一定是树。那么只需要选 \(n-1\) 条边使图连通，求最小代价。不难发现只要保证结果不出现环就可能是答案。

考虑贪心求解，对于当前生成树构成的连通块，每次向外拓展代价最小的边，并合并对应的节点即可。注意，如果两个节点都在连通块内，那么它们之间不能再加边，否则一定会出现环。

暴力做的话可以做到 $ O(n^2+m) $ ，用单调队列维护可以做到 $ O( (n+m)\log n) $ ，具体实现类似于dijkstra

struct node{
	int x;ll y;
	bool operator<(node an)const{
		return y>an.y;
	}
};
priority_queue<node>q;
void prim(){
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	q.push({1,0});
	while(!q.empty()){
		node u=q.top();q.pop();
		if(vis[u.x])continue;
		vis[u.x]=1;
		ans+=u.y;
		for(int i=head[u.x];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]>e[i].val){
				dis[v]=e[i].val;
				q.push({v,e[i].val});
			}
		}
	}
}

Kruskal

一种更常用的算法。

由于只要保证生成树上没有环，在此基础上求最小代价和。将所有边按边权升序排序，依次遍历，如果两点不在同一连通块就合并，并查集维护。复杂度 $ O(m\log m) $ 。可以发现这就是最优答案。

struct edge{
	int x,y,val;
}e[N];
bool cmp(edge fir,edge sec){
	return fir.val<sec.val;
}
int find(int x){
	if(x==fa[x])return x;
	else return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
}
void kruskal(){
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(find(e[i].x)!=find(e[i].y)){
			ans+=e[i].val;
			merge(e[i].x,e[i].y);
		}
	}
}

Boruvka

最近刚学的菠萝算法。

初始时，我们把每个节点看做一个连通块，进行如下操作：

1. 对于每个连通块，寻找连接它和另一个不同的连通块的最小边

2. 将最小边连接的两个连通块合并，并统计答案（这里每次合并前都要判断是否属于同一连通块）

3. 如果所有节点都合并到同一连通块，退出

有点像前两种算法结合起来。正确性是显然的，因为每次连通块向外连边一定是当前最优也是以后最优的。每次合并连通块数量至少减半，复杂度为 $ O(m\log n) $

struct node{
	int x,y;
}minn[N];
int find(int x){
	if(x==fa[x])return x;
	else return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
}
bool check(){
	for(int i=2;i<=n;i++){
		if(find(i)!=find(i-1))return 1;
	}
	return 0;
}
void Boruvka(){
	while(check()){
		for(int i=1;i<=n;i++)minn[i].y=inf;
		for(int i=1;i<=n;i++){
			int fx=find(i);
			for(int j=head[i];j;j=e[j].nxt){
				if(fx!=find(e[j].to)&&e[j].val<minn[fx].y)minn[fx]={e[j].to,e[j].val};
			}
		}
		for(int i=1;i<=n;i++){
			int fx=find(i);
			if(fx!=find(minn[fx].x)){
				merge(fx,minn[fx].x);
				ans+=minn[fx].y;
			}
		}
	}
}

Boruvka 在实现难度和常数方面不如前两种算法，但是在某一类题目中有明显优势：给定 \(n\) 个点，每个点都有权值，并且两两之间可以任意连边，边权以某种方式定义且与两个端点的权值有关，求最小生成树的边权和。可以参考练习题。

练习题

限速

题意

给定 \(n\) 个点， \(m\) 条带权边的连通图，首先选择 $ n-1 $ 条边构成一棵树，其次，可以操作一次使一条边权加1或减1，使的生成树的最大边权 恰好 为 \(k\) ，求最小操作次数。 $ n,m \le 2 \times 10^5 ,k\le 1\times 10^9 $

题解

为叙述方便，我们定义权值不超过 \(k\) 的边为A边，其余为B边，考虑选择的边有两种情况：

1. 只有A边

2. 存在B边

第一种情况代价最小的方案是把边权最大的A边加到 \(k\) ；第二种情况最小代价是把B边都减至 \(k\) 。

先判断只有A边能否构成生成树，如果可以，一定能选择边权最大的A边作为候选答案。考虑加入一条B边，在形成的生成树一定会出现一个环，断掉环上任意一条A边即可。 $ ans = \min \{ k- \max a_i \ , \min b_i -k \} $

如果A边不能构成生成树，直接跑最小生成树使最大权最小。

排列最小生成树 (pmst)

题意

给定一个 \(1\) 到 \(n\) 的排列 \(p\) 。构造一个有 \(n\) 个节点的无向完全图，定义节点 \(i\) 和节点 \(j\) 的边权为 $ | p_i-p_j | \times | i-j | $ ，求最小生成树的边权和。$ n\le 5 \times 10^4 $

题解

发现神秘结论即可

首先注意到答案不会很大，因为一定有这样的一种构造：生成树是一条编号连续的链，这样每条边的权值都不会超过 $ n $ 。再考虑正解，发现每个点只有 $ O(\sqrt N) $ 条边是有意义的，其它边权都超过 \(n\) 了。所以只要先按 \(i\) 排序，取相邻的 $ \sqrt n $ 个点建边，再按 $ p_i $ 排序，重复操作，跑 kruskal 。排序的时候建议桶排， sort 和不优良的实现都会T飞的。

星际联邦

题意

一个 $ n $ 个节点的完全图，第 $ i $ 个节点的权值为 $ u_i $ （可能为负），从 $ i $ 向 $ j $ 的边权为 $ u_j-u_i $ （要求 $ i < j $ ），求最小生成树边权和。 $ n\le 3 \times 10^5 $

题解

考虑 Boruvka 怎么做，难点在于 $ O(n) $ 的复杂度求出每个连通块向外的最小边。发现对于节点 $ i $ ，与其不属于同一连通块且边权最小的点只可能有两个 : 向前最小的 $ u_j ( j < i ,f_j \neq f_i ) $ 和向后最大的 $ u_j ( j>i,f_j \neq f_i ) $ 。发现 $ f_i \neq f_j $ 很难做到，这里积累一个 trick ，记录 $ minn[0][i] $ 为 $ [1,i) $ 中最小值的编号 ，$ minn[1][i] $ 为与 $ minn[0][i] $ 属于不同连通块的最小值的编号，这样就可以快速求出与 $ i $ 不在同一连通块的最大值。对于 $ j>i $ 同理。实现有些细节，其它没了。