Skip to main content

生成树

参考资料​

最小生成树​

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

算法对比​

nn 代表图的点数，mm 代表图的边数。

算法名称时间复杂度
Kruskal 算法O(mlog⁡m)O(m\log m)
Prim 算法O((n+m)log⁡n)O((n+m)\log n)
Boruvka 算法O(mlog⁡n)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 【模板】最小生成树

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

Code (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 口袋的天空

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

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

Code (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 国有 nn 座城市，编号从 11 到 nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。

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

Code (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 星际导航

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

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

Code (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;
}