最小生成樹學習筆記

定義

最小生成樹是指給定一個帶權連通圖 G，如果裡面有一個子圖 G' 中的邊權和加起來最小並且使得所有的點都能兩兩相通。

性質

從上述的定義可以看出，最小生成樹有以下性質：

如果圖 G 中有 n 個點的話，G'中的邊數為 n-1 且 G' 中不含有環。
最小生成樹可能是一個，也可能是多個。

還有一些複雜的性質感興趣的可以自行百度。

kruskal 演演算法

前置知識：並查集。

kruskal 演演算法的基本思想就是貪心，該演演算法的流程也很簡單。

首先我們需要將所有的邊進行排序，然後列舉每一條邊，如果當前的邊連結的兩個點早已經間接或直接相連，我們就直接跳過，不連這條邊，如果連滿了 n-1 條邊就直接退出迴圈，然後我們所選的邊就構成了一棵最小生成樹。

在判斷當前邊的兩點是否已經相連的辦法可以用並查集來判斷，也是比較方便的做法。

根據其定義可以想到，我們要貪心的話，就得先加入邊權小的邊，假設只有兩個點，那他的最小生成樹就是兩點之間邊權最小的邊構成，當到了三個點之後，就是從前面已經連結的所有邊中覆蓋的點與第三個點相連的邊中挑一條邊權最小的邊來連，因為如果要是想要把第三個點連進去，就必須要與之前的聯通圖中的任意一點連一條邊，經過這樣不斷的擴大，最終會以最小的代價連進所有點。在演演算法流程中，其當前連線的邊是必定有一個點是在聯通圖中，必有一個點未連進聯通圖中，而當前邊又是剩下的邊中邊權最小的，所以一定是原圖中一棵最小生成樹的邊。

以上不理解也沒關係~~反正是我胡扯的背板子就好了~~

P3366 【模板】最小生成樹

code：

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,f[N],num,ans;
struct sb{int x,y,w;}e[N];
inline int cmp(sb a,sb b){return a.w<b.w;}
inline int fid(int x){if(x==f[x])return x;else return f[x]=fid(f[x]);}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)cin>>e[i].x>>e[i].y>>e[i].w;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int xx=fid(e[i].x);
		int yy=fid(e[i].y);
		if(xx==yy)continue;
		f[xx]=yy;
		ans+=e[i].w;
		num++;
		if(num==n-1)break;
	}
	if(num==n-1)cout<<ans<<endl;
	else cout<<"orz"<<endl;
	return 0;
}

1487：【例 2】北極通訊網路

題目說的有點繞，但仔細讀完就會發現意思是讓你找一棵最小生成樹，其中有 k 個點是不必連入的，也就是等同於讓你連 n-k 條邊。

code：

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
double ans;
int n,k,fa[N],num,m;
struct sb{int x,y;}e1[N];
struct SB{int u,v;double w;}e[N<<5];
inline int cmp(SB a,SB b){return a.w<b.w;}
inline int fid(int x){if(fa[x]==x)return x;return fa[x]=fid(fa[x]);}
inline double js(sb u,sb v){return sqrt(pow(u.x-v.x,2)+pow(u.y-v.y,2));}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)fa[i]=i,cin>>e1[i].x>>e1[i].y;
	for(int i=1;i<=n;i++)
	  for(int j=i;j<=n;j++)
	    e[++m].u=i,e[m].v=j,e[m].w=js(e1[i],e1[j]);
	sort(e+1,e+m+1,cmp); 
	for(int i=1;i<=m;i++)
	{
		int xx=fid(e[i].u);
		int yy=fid(e[i].v);
		if(xx==yy)continue;
		fa[xx]=yy;num++;
		ans=max(e[i].w,ans);
		if(num==n-k)break;
	}
	printf("%.2lf\n",ans);
	return 0;
}

1488：新的開始

題目中如果要是是隻有一個固定的發電站的話，那就是純板子了，但是這個也不難，我們考慮一下如果只連邊的話，這個電網裡面是沒有電的，所以我們需要開一個點 n+1 來存放發電站，然後把題目中的在當前點建發電站轉化成當前點直接和發電站連邊，也就是從 n+1 向每一個點連一條邊邊權為 v，這樣就相當於連 n 條邊。

code：

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,fa[N],mp[500][500],val[N],num,ans;
struct sb{int u,v,w;}e[N];
inline int cmp(sb a,sb b){return a.w<b.w;}
inline int fid(int x){if(fa[x]==x)return x;return fa[x]=fid(fa[x]);}
signed main()
{
	cin>>n;
	for(int i=1;i<=n+1;i++)fa[i]=i;
	for(int i=1;i<=n;i++)cin>>val[i],e[++m].u=n+1,e[m].v=i,e[m].w=val[i];
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    cin>>mp[i][j],e[++m].u=i,e[m].v=j,e[m].w=mp[i][j];
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int xx=fid(e[i].u);
		int yy=fid(e[i].v);
		if(xx==yy)continue;
		fa[xx]=yy;
		num++;
		ans+=e[i].w;
		if(num==n)break ;
	}
	cout<<ans<<endl;
	return 0;
}

prim 演演算法

由於 prim 本人不是很熟練此部分參考 https://www.cnblogs.com/bcoier/p/10293059.html
~~我看到裡面有 kruskal 的流程圖所以也粘過來了~~

這個演演算法的流程本質也是貪心，首先需要我們選定任意一個節點作為根節點，然後往下開始擴充套件，在每一次擴充套件的過程中都選用待選邊（連結 u，v）中權值最小的邊進行擴充套件，然後將除此邊外與 v 相連的所有邊都放入待選邊，如果此時加入的邊與 v 相連的點中有的點實際上是已經有待定邊相連了，就更新最短路，也就是取個 min，讓選取的邊權和儘可能的小。

可以看看上面部落格的圖：

P3366 【模板】最小生成樹

沒錯就是上面那道，結合註釋和圖理解一下 prim 的流程。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define N 1000100
using namespace std;
int n,m,head[N],dis[N],cnt,num,now=1,ans,vis[N];
//dis表示從已經在連通塊裡的點到當前點的最短距離，vis標記是否在連通圖內，now是當前節點 
struct sb{int u,v,w,next;}e[N];
inline void add(int u,int v,int w)//鏈式前向星存圖 
{
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	for(int i=2;i<=n;i++)
	  dis[i]=INF;//dis一開始都設極大值，後面要取min 
	for(int i=head[1];i;i=e[i].next)//列舉與起點相連的邊 
	  dis[e[i].v]=min(dis[e[i].v],e[i].w);//更新dis，取min 
	while(1)//只要沒完成就一直找 
	{
		int minn=INF;//存放當前的最小的沒在連通圖裡的dis的值 
		vis[now]=1;//當前點加入連通圖，now存下標 
		for(int i=1;i<=n;i++)//列舉n個點 
		  if(!vis[i]&&minn>dis[i])//找最小的不在連通圖的dis 
		    now=i,minn=dis[i];//存值 
		ans+=minn;//加入當前邊 
		for(int i=head[now];i;i=e[i].next)//列舉每一個與之相連的邊 
		  if(dis[e[i].v]>e[i].w&&!vis[e[i].v])//更新dis，除在連通圖的點之外 
		    dis[e[i].v]=e[i].w;
		num++;//加邊數+1 
		if(num==n-1||minn==INF)break;//如果到n-1條邊了或者minn沒值了 
	}
	if(num==n-1)cout<<ans<<endl;//輸出答案 
	else cout<<"orz"<<endl;
	return 0;
}

由於 prim 不如 kruskal 好寫所以我只寫了一個模板。

關於他倆誰快的問題，稠密圖 prim 快一點，稀疏圖 kruskal 快一點。

嚴格次小生成樹

本來這個是不打算寫的了，但是想了想還是來一發吧。

屠龍寶刀點選就送

看完題目發現要求的不是最小生成樹，而是一個新名詞：嚴格次小生成樹，也就是邊權和嚴格第二小的生成樹。

首先題目說的是嚴格次小，也就是說，如果換了一條邊，但是邊權和沒變，這種是不算嚴格次小生成樹的。

\(mst\) 表示當前最小生成樹的邊權和， \(Mst\) 表示嚴格次小生成樹的邊權和，\(maxUV\) 表示 u 到 v 的路徑上的最大邊權，\(MaxUV\) 表示從 u 到 v 的路徑上的次大的邊權。

所以我們得到兩種情況：

當前要加入的邊 \(e\ne maxUV\)，那麼得到一個 \(Mst\) 的侯選值 \(mst-maxUV+e\)
當前要加入的邊 \(e = maxUV\)，那麼得到一個 \(Mst\) 的侯選值 \(mst-MaxUV+e\)

然後問題就轉化為了如何求 \(maxUV\) 和 \(MaxUV\)。

我們可以很容易想到暴力會 T 飛，所以我們選用倍增來解決，具體就是維護兩個倍增陣列 \(max1[i][j]\) 存放 i 點向上跳 \(2^{j}\) 步以後到的點之間的最大邊權，\(max2[i][j]\) 存放 i 點向上跳 \(2^{j}\) 步以後到的點之間的次大邊權，具體看下面程式碼的註釋。

梳理一下流程：

先跑一邊最小生成樹
預處理出倍增陣列 \(max1\)，\(max2\)。
倍增處理當前要加入的邊 e 的起始點在最小生成樹上的最大邊權。

最後對所有的待選值取個 min 即可。

code：

#include<bits/stdc++.h>
#define int long long
#define INF (1ll<<62)
#define M 1000100
#define N 400010
using namespace std;
struct sb{int u,v,w,bt;}e[M];
int dep[N],f[N][21],max1[N][21],max2[N][21];
int n,m,mst,tot,head[M<<1],nxt[M<<1],v[M<<1],w[M<<1],fa[N];
inline int cmp(sb a,sb b){return a.w<b.w;}
inline int fid(int x){return fa[x]==x?x:fa[x]=fid(fa[x]);}
inline void add(int u,int v1,int w1){nxt[++tot]=head[u],head[u]=tot,v[tot]=v1,w[tot]=w1;}
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void kruskal()//最小生成樹板子，不會請退役 
{
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(fid(u)==fid(v))continue;
		mst+=w;
		e[i].bt=1;
		add(u,v,w);
		add(v,u,w);
		fa[fid(u)]=fid(v);
	}
}
inline void dfs(int x)//dfs預處理 
{
	for(int i=1;i<=18;i++)//處理倍增陣列 
	{
		f[x][i]=f[f[x][i-1]][i-1];//處理倍增的父親節點 
		max1[x][i]=max(max1[x][i-1],max1[f[x][i-1]][i-1]);//處理最大值，直接對兩個區間取max 
		max2[x][i]=max(max2[x][i-1],max2[f[x][i-1]][i-1]);//先和上面一樣取max 
		if(max1[x][i-1]!=max1[f[x][i-1]][i-1])//如果要是最大值的兩個區間內的最大值不同 
		  max2[x][i]=max(max2[x][i],min(max1[x][i-1],max1[f[x][i-1]][i-1]));//從兩個最大值裡選個次小的 
	}
	for(int i=head[x];i;i=nxt[i])//遍歷與當前點相連的邊 
	{
		if(dep[v[i]])continue;//走過了就算了 
		f[v[i]][0]=x;//標記父節點 
		max1[v[i]][0]=w[i];//標記最大邊權 
		max2[v[i]][0]=-INF;//標記次大邊權 
		dep[v[i]]=dep[x]+1;//計算深度 
		dfs(v[i]);//繼續搜 
	}
}
inline int LCA(int x,int y)//倍增求lca，不會請退役 
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=18;i>=0;i--)
	  if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if(x==y)return x;
	for(int i=18;i>=0;i--)
	  if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int qmax(int x,int y,int z)//求x到y的邊權最大值，z是要加進去的邊權 
{
	int minn=-INF;//先設個最小值後面取min（設不設都行其實 
	for(int i=18;i>=0;i--)//倍增往上跳 
	{
		if(dep[f[x][i]]>=dep[y])//如果跳的時候不會超過就更新 
		{
			if(z!=max1[x][i])minn=max(minn,max1[x][i]);//情況1最大邊權不等於z 
			else minn=max(minn,max2[x][i]);//情況二 最大邊權等於z 
			x=f[x][i];//更新點的編號 
		}
	}
	return minn;//返回查到的需要替換的邊權 
}
signed main()
{
	n=read(),m=read(); 
	for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),e[i].w=read();//輸入邊的資訊 
	kruskal();//跑一邊最小生成樹 
	dep[1]=1;//賦初值第一個點深度為1 
	dfs(1);//從1開始往下搜 
	int Mst=INF;//存放次小生成樹的值 
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u,v=e[i].v,w=e[i].w;//起點終點邊權 
		if(e[i].bt)continue;//如果是樹邊的話就跳過 
		int lca=LCA(u,v);//求LCA 
		int maxx=qmax(u,lca,w);//求出u到lca的邊權最大值 
		int maxy=qmax(v,lca,w);//求出v到lca的邊權最大值 
		Mst=min(Mst,mst-max(maxx,maxy)+w);//對於每一個去掉邊權最大值取當前邊權的方案取min 
	}
	cout<<Mst<<endl;//輸出答案 
	return 0;
}