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 算法​

409 Bcpp
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 重构树​

473 Bcpp
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）

洛谷 P1195 口袋的天空

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

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

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

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

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

洛谷 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} 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。