生成树

参考资料

最小生成树

无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

算法对比

$n$ 代表图的点数， $m$ 代表图的边数。

算法名称	时间复杂度
Kruskal 算法	$O(m\log m)$
Prim 算法	$O((n+m)\log n)$
Boruvka 算法	$O(m\log n)$

Kruskal 算法

struct Edge
{
	int u,v,w;
	bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n)
{
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(E.begin(),E.end());
	int ans=0,cnt=0;
	for(auto [u,v,w]:E)
	{
		if(cnt==n-1)break;
		int x=find(u),y=find(v);
		if(x==y)continue;
		fa[x]=y;
		ans+=w;
		cnt++;
	}
	return cnt==n-1?ans:-1;
}

瓶颈生成树

Kruskal 重构树

struct Edge
{
	int u,v,w;
	bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
vector<int> G[N];
int fa[N],val[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n)
{
	for(int i=1;i<=n<<1;i++)fa[i]=i;
	sort(E.begin(),E.end());
	int cnt=0,t=n;
	for(auto [u,v,w]:E)
	{
		if(cnt==n-1)break;
		int x=find(u),y=find(v);
		if(x==y)continue;
		fa[x]=fa[y]=++t;
		G[t].push_back(x);
		G[t].push_back(y);
		val[t]=w;
		cnt++;
	}
	return t;
}

例题

洛谷 P3366 【模板】最小生成树

给定一张 $n$ 个点 $m$ 条边的无向图，求出最小生成树。如果该图不连通则输出 orz。（ $n\le5000,m\le2\times10^5$ ）

代码（1）

#include <bits/stdc++.h>
using namespace std;

const int N=5005;
struct Edge
{
	int u,v,w;
	bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n)
{
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(E.begin(),E.end());
	int ans=0,cnt=0;
	for(auto [u,v,w]:E)
	{
		if(cnt==n-1)break;
		int x=find(u),y=find(v);
		if(x==y)continue;
		fa[x]=y;
		ans+=w;
		cnt++;
	}
	return cnt==n-1?ans:-1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		E.push_back({u,v,w});
	}
	int ans=kruskal(n);
	if(ans!=-1)cout<<ans<<'\n';
	else cout<<"orz"<<'\n';
	return 0;
}

洛谷 P1195 口袋的天空

给你云朵的个数 $N$ ，再给你 $M$ 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 $K$ 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

代码（1）

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
struct Edge
{
	int u,v,w;
	bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
int fa[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n,int k)
{
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(E.begin(),E.end());
	int ans=0,cnt=0;
	for(auto [u,v,w]:E)
	{
		if(cnt==n-k)break;
		int x=find(u),y=find(v);
		if(x==y)continue;
		fa[x]=y;
		ans+=w;
		cnt++;
	}
	return cnt==n-k?ans:-1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,k;
	cin>>n>>m>>k;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		E.push_back({u,v,w});
	}
	int ans=kruskal(n,k);
	if(ans!=-1)cout<<ans<<'\n';
	else cout<<"No Answer"<<'\n';
	return 0;
}

洛谷 P1967 [NOIP 2013 提高组] 货车运输

A 国有 $n$ 座城市，编号从 $1$ 到 $n$ ，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

代码（1）

#include <bits/stdc++.h>
using namespace std;

const int N=20005;
struct Edge
{
	int u,v,w;
	bool operator<(const Edge &x) const{return w>x.w;}
};
vector<Edge> E;
vector<int> G[N];
int fa[N],val[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n)
{
	for(int i=1;i<=n<<1;i++)fa[i]=i;
	sort(E.begin(),E.end());
	int cnt=0,t=n;
	for(auto [u,v,w]:E)
	{
		if(cnt==n-1)break;
		int x=find(u),y=find(v);
		if(x==y)continue;
		fa[x]=fa[y]=++t;
		G[t].push_back(x);
		G[t].push_back(y);
		val[t]=w;
		cnt++;
	}
	return t;
}
int f[N],son[N],siz[N],dep[N],top[N];
void dfs1(int u)
{
	siz[u]=1;
	dep[u]=dep[f[u]]+1;
	for(auto v:G[u])
	{
		f[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	if(son[u])dfs2(son[u],t);
	for(auto v:G[u])
	{
		if(v==son[u])continue;
		dfs2(v,v);
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=f[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		E.push_back({u,v,w});
	}
	n=kruskal(n);
	for(int i=1;i<=n;i++)
	{
		if(find(i)==i)
		{
			dfs1(i);
			dfs2(i,i);
		}
	}
	int q;
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		cout<<(find(x)==find(y)?val[lca(x,y)]:-1)<<'\n';
	}
	return 0;
}

洛谷 P2245 星际导航

$\text{sideman}$ 做好了回到 $\text{Gliese}$ 星球的硬件准备，但是 $\text{sideman}$ 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 $N$ 个顶点和 $M$ 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

$\text{sideman}$ 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 $(A, B)$ ， $\text{sideman}$ 想知道从顶点 $A$ 航行到顶点 $B$ 所经过的最危险的边的危险程度值最小可能是多少。作为 $\text{sideman}$ 的同学，你们要帮助 $\text{sideman}$ 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

代码（1）

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
struct Edge
{
	int u,v,w;
	bool operator<(const Edge &x) const{return w<x.w;}
};
vector<Edge> E;
vector<int> G[N];
int fa[N],val[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int kruskal(int n)
{
	for(int i=1;i<=n<<1;i++)fa[i]=i;
	sort(E.begin(),E.end());
	int cnt=0,t=n;
	for(auto [u,v,w]:E)
	{
		if(cnt==n-1)break;
		int x=find(u),y=find(v);
		if(x==y)continue;
		fa[x]=fa[y]=++t;
		G[t].push_back(x);
		G[t].push_back(y);
		val[t]=w;
		cnt++;
	}
	return t;
}
int f[N],son[N],siz[N],dep[N],top[N];
void dfs1(int u)
{
	siz[u]=1;
	dep[u]=dep[f[u]]+1;
	for(auto v:G[u])
	{
		f[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	if(son[u])dfs2(son[u],t);
	for(auto v:G[u])
	{
		if(v==son[u])continue;
		dfs2(v,v);
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=f[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		E.push_back({u,v,w});
	}
	n=kruskal(n);
	for(int i=1;i<=n;i++)
	{
		if(find(i)==i)
		{
			dfs1(i);
			dfs2(i,i);
		}
	}
	int q;
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		if(find(x)==find(y))cout<<val[lca(x,y)]<<'\n';
		else cout<<"impossible"<<'\n';
	}
	return 0;
}

参考资料​

最小生成树​

算法对比​

Kruskal 算法​

瓶颈生成树​

Kruskal 重构树​

例题​

洛谷 P3366 【模板】最小生成树​

洛谷 P1195 口袋的天空​

洛谷 P1967 [NOIP 2013 提高组] 货车运输​

洛谷 P2245 星际导航​

参考资料

最小生成树

算法对比

Kruskal 算法

瓶颈生成树

Kruskal 重构树

例题

洛谷 P3366 【模板】最小生成树

洛谷 P1195 口袋的天空

洛谷 P1967 [NOIP 2013 提高组] 货车运输

洛谷 P2245 星际导航