一個(gè) \(n\) 個(gè)點(diǎn)，\(m\) 條無(wú)向邊的圖的生成樹(shù)，通俗來(lái)說(shuō)，就是保留 \(n-1\) 條邊使得這些被保留的邊能構(gòu)成一棵 \(n\) 個(gè)點(diǎn)的樹(shù)。若邊帶邊權(quán)，則定義最小生成樹(shù)為被保留的邊邊權(quán)和最小的生成樹(shù)。這樣的生成樹(shù)可能有多個(gè)。

嚴(yán)謹(jǐn)來(lái)說(shuō)就是對(duì)于邊集 \(E\)，從中選出一個(gè)子集 \(F\) 使得 \(F\) 能構(gòu)成一棵 \(n\) 個(gè)點(diǎn)的樹(shù)。其中權(quán)值和最小的 \(F\) 為最小生成樹(shù)。

解決這類問(wèn)題，常用算法有 Kruskal 算法、Prim 算法和Boruvka 算法。

Kruskal 算法

能在 \(O(m\log m)\) 的復(fù)雜度解決該問(wèn)題。

算法流程

將 \(m\) 條邊按邊權(quán)從小到大排序。依次遍歷每一條邊，如果加入該邊后生成樹(shù)會(huì)形成環(huán)就扔掉該邊。用并查集維護(hù)該過(guò)程。

正確性證明

使用歸納法。

假設(shè)當(dāng)前狀態(tài)成立，考慮下一條加入的邊。

設(shè)當(dāng)前最小生成樹(shù)為 \(T\)，已選出的邊集為 \(F\)，下一條加入 \(F\) 的邊為 \(e\)。

如果 \(e\in T\)，則成立。

否則 \(T+e\) 一定存在一個(gè)環(huán)。找到這個(gè)環(huán)上有且僅有一條不屬于 \(F\) 的邊 \(f\)。

設(shè) \(w(k)\) 為邊 \(k\) 的權(quán)值。首先一定有 \(w(f)\ge w(e)\)，不然 \(f\) 會(huì)比 \(e\) 優(yōu)先考慮，不會(huì)出現(xiàn) \(e\in F\) 且 \(f\notin F\)。

其次一定有 \(w(f)\le w(e)\)，不然 \(T+e-f\) 較 \(T\) 而言是一棵更優(yōu)的生成樹(shù)，不符合 \(T\) 的定義。

而當(dāng) \(w(f)=w(e)\) 時(shí)，\(F\) 并不比 \(T\) 劣。

綜上得證。

代碼實(shí)現(xiàn)

struct edge
{
	int u,v,w;
}a[M];
bool cmp(edge a,edge b){return a.w<b.w;}
int find(int x)
{
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void unionn(int x,int y)
{
	int xx=find(x),yy=find(y);
	fa[xx]=yy;
}
int Kruskal()
{
	sort(a+1,a+m+1,cmp);
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int u=a[i].u,v=a[i].v;
		if(find(u)==find(v)) continue;
		ans+=a[i].w;
		unionn(u,v);
	}
	return ans;
}

Prim 算法

能在 \(O((n+m)\log n)\) （二叉堆）、\(O(n\log n+m)\) （Fib 堆）的時(shí)間復(fù)雜度解決該問(wèn)題。

實(shí)際在稠密圖上運(yùn)行效率略微比 Kruskal 算法快。

算法流程

維護(hù)一個(gè)點(diǎn)集 \(S\)。初始選定一個(gè)點(diǎn) \(u\) 使得 \(S=\{u\}\)。

每一次找到不在 \(S\) 中且距離 \(S\) 中任意一個(gè)點(diǎn)最近的一個(gè)點(diǎn)。然后加入 \(S\)。加入最小生成樹(shù)的邊就是這個(gè)點(diǎn)與原先 \(S\) 中最近一個(gè)點(diǎn)的連邊。

這個(gè)過(guò)程可以用堆優(yōu)化。

正確性證明

類似 Kruskal 算法。

代碼實(shí)現(xiàn)

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int Prim()
{
	int res=0;
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[1]=0;
	vis[1]=1;
	q.push({0,1});
	while(!q.empty())
	{
		int u=q.top().second,d=q.top().first;
		if(d!=dis[u]||vis[u]) continue;
		vis[u]=1;
		res+=d;
		for(int i=head[u];i!=0;i=a[i].nxt)
		{
			int v=a[i].v,w=a[i].w;
			if(w<dis[v]) dis[v]=w,q.push({w,v});
		}
	}
	return res;
}

Boruvka 算法

時(shí)間復(fù)雜度 \(O(m\log n)\)。較 Prim 算法在更加稠密的圖上（如完全圖）有更優(yōu)效率。

因?yàn)槊恳惠啿僮鲿r(shí)，每一個(gè)節(jié)點(diǎn)所在的連通塊都已知，且在這一輪操作結(jié)束前不會(huì)更改每一個(gè)節(jié)點(diǎn)所在的連通塊。于是能解決一些 Kruskal 算法和 Prim 算法無(wú)法解決的特殊問(wèn)題。

算法流程

初始時(shí)將 \(n\) 個(gè)點(diǎn)視為 \(n\) 個(gè)集合。現(xiàn)在不斷進(jìn)行合并集合。

定義一輪操作如下：

對(duì)于當(dāng)前每一個(gè)集合，找到距離它最近的一個(gè)集合（定義集合 \(S,T\) 間的距離為 \(\min w(u,v)( u\in S,v\in T)\)。然后將每一個(gè)集合與離它最近的集合合并成一個(gè)集合。加入最小生成樹(shù)的邊為兩集合之間最短的邊。

不斷進(jìn)行一輪操作，直到合并成一個(gè)集合。

可以發(fā)現(xiàn)，最多進(jìn)行 \(O(\log n)\) 輪操作。因?yàn)樵O(shè)當(dāng)前有 \(k\) 個(gè)集合，一輪操作后，最多還剩 \(\lceil\frac k2\rceil\) 個(gè)集合。

每一輪操作遍歷所有邊依次，然后處理每一個(gè)集合最近的集合。因此時(shí)間復(fù)雜度為 \(O(m\log n)\)。

一些細(xì)節(jié)說(shuō)明：

問(wèn)：如何保證我們不會(huì)在一輪中加入一個(gè)環(huán)？

答：集合間最短的邊的兩端點(diǎn)所在集合的最近集合一定是彼此。所以一輪中最多會(huì)加入 \(k-1\) 條邊。

但是有一個(gè)例外：如果存在邊權(quán)相同的情況，我們可能會(huì)在一輪中加入一個(gè)環(huán)。

因此當(dāng)邊權(quán)相同時(shí)，我們一定要把它們按第二關(guān)鍵字區(qū)分開(kāi)。

代碼實(shí)現(xiàn)

int ans=0,fa[N];
pair<int,int> dis[N];
int find(int x)
{
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void unionn(int x,int y)
{
	int xx=find(x),yy=find(y);
	fa[xx]=yy;
}
void Boruvka()
{
	for(int i=1;i<=n;i++) dis[i]={inf,0};
	for(int i=1;i<=m;i++)
	{
		int u=a[i].u,v=a[i].v,w=a[i].w;
		if(find(u)==find(v)) continue;
		dis[find(u)]=min(dis[find(u)],{w,v});
		dis[find(v)]=min(dis[find(v)],{w,u});
	}
	for(int u=1;u<=n;u++)
	{
		int v=dis[u].second;
		if(v&&find(v)!=find(u))
		{
			unionn(u,v);
			ans+=dis[u].first;
		}
	}
}
bool check()
{
	for(int i=2;i<=n;i++) if(find(i)!=find(1)) return false;
	return true;
}
int main()
{
    for(int i=1;i<=n;i++) fa[i]=i;
	while(!check()) Boruvka();
}

好題記錄

D 【0504 B組】天空璋

題目鏈接

題目描述：

給定一個(gè) \(n\times n\) 的二維數(shù)組 \(a\)，初始全為 \(0\)。有 \(m\) 次修改，第 \(i\) 次讓 \(a_i\le x\le b_i,c_i\le y\le d_i\) 的 \(a_{x,y}\) 加上 \(w\)。

所有修改完成后，考慮一張 \(n\) 個(gè)點(diǎn)的完全圖，\(i,j\) 之間連邊的權(quán)值為 \(a_{i,j}+a_{j,i}\)。請(qǐng)求出這張完全圖的最小生成樹(shù)的邊權(quán)和。

\(1\le n,m\le 10^5,1\le a_i,b_i,c_i,d_i\le n,0\le |w|\le 10^6\)。

很容易有 \(O(n^2\log (n^2)+m)\) 的二維差分+Kruskal/Prim的做法。但是該做法難以拓展。

邊 \((i,j)\) 邊權(quán)為 \(a_{i,j}+a_{j,i}\)，過(guò)于復(fù)雜，考慮更改一下。將每一次操作對(duì) \(a_i\le x\le b_i,c_i\le y\le d_i\) 的 \(a_{x,y}\) 加上 \(w\) 向?qū)蔷€進(jìn)行一次對(duì)稱的操作。即每一次操作，在原來(lái)的基礎(chǔ)上，再將 \(c_i\le x\le d_i,a_i\le y\le b_i\) 的 \(a_{x,y}\) 加上 \(w\)。這樣邊 \((i,j)\) 的邊權(quán)就變?yōu)?\(a_{i,j}\) 了。

考慮用 Boruvka 算法。那么現(xiàn)在目標(biāo)是求出一個(gè)連通塊最近的連通塊。

如果我們知道所有的 \(a_{i,j}\)，那么對(duì)于連通塊 \(S\)，離它最近的連通塊的距離即為 \(u\in S,\min_{v\notin S} a_{u,v}\)，找到最小值對(duì)應(yīng)的 \(v\) 所在連通塊即可。

設(shè) \(col_u\) 為當(dāng)前輪操作中 \(u\) 所在的連通塊編號(hào)。則我們需要處理出第 \(u\) 行中的 \(\min_{col_v\neq col_u} a_{u,v}\)。如何處理這樣的 \(v\)？

其實(shí)對(duì)于每一行，我們只需要處理出 \(v\) 滿足 \(a_{u,v}\) 是本行最小的，和 \(k\) 滿足 \(a_{u,k}\) 是本行滿足 \(col_v\neq col_k\) 中最小的。也就相當(dāng)于最小值，以及與最小值不在同一連通塊的次小值。這個(gè)東西是可以用線段樹(shù)處理的。

考慮用掃描線處理出每一行的 \(a\) 值，同時(shí)處理出上述值。然后第 \(u\) 行就判斷是否有 \(col_u\neq col_v\)，如果有就連 \((u,v)\)，否則連 \((u,k)\)。

于是可以在 \(O(n\log n)\) 處理一輪操作。總共有 \(O(\log n)\) 輪，于是總時(shí)間復(fù)雜度為 \(O(n\log^2 n)\)，可以通過(guò)本題。

提交記錄

本題主要利用了 Boruvka 算法在一輪操作中，每個(gè)點(diǎn)所在的連通塊不會(huì)發(fā)生改變的性質(zhì)來(lái)處理問(wèn)題。