最小生成树

P3366 【模板】最小生成树

前置知识:

链式前向星,dijkstra

定义

生成树:连通且不含环的子图,

其节点数与主图相同,边数为点数减一

在其中任意添加一条边,生成树就会形成环

最小生成树:所有生成树中边权和最小的

实现

解决最小生成树常见有两种方法,Kruskal和Prim,定义边数为m,点数为n

Krusal时间复杂度O(mlog2m), sortO(mlog2n),并查集O(m)
Prim时间复杂度O(mlog2n),加优先队列优化的情况下

krusal全局贪心,Prim局部贪心(跟dij基本一样,dijkstra在一篇文章里同时提出了dij和krusal)

Kruskal

思路:

全局中找边权最小的边,然后添加进去,如果形成环就不加.边数达到n-1时停止,或者点数m

我们通过排序和并查集来实现

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 5e3 + 5, M = 2e5 + 5;
struct Edge{ //存下边就得了,省的麻烦
	int u, v, w;
}edge[M];
int fa[N];

int find_set(int x){
	return x == fa[x] ? x : (fa[x] = find_set(fa[x]));
}

int n,m;
void kruskal(){
	sort(edge + 1, edge + 1 + m, [](Edge a, Edge b){return a.w < b.w;});
	for(int i = 1; i <= n; i++) fa[i] = i;
	int ans = 0, cnt = 0;
	for(int i = 1; i <= m; i++){
		if(cnt == n - 1) break; 
		int a = find_set(edge[i].u);
		int b = find_set(edge[i].v);
		if(a == b) continue;
		else{
			ans += edge[i].w;
			fa[a] = b;
			cnt++;
		}
	}
	if(cnt == n - 1) cout<<ans;
	else cout<<"orz";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i = 1; i <= m; i++){
		cin>>edge[i].u>>edge[i].v>>edge[i].w;
	}
	kruskal();
	return 0;
}

Prim

思路:

纯纯和dij基本一模一样,只不过prim不用更新集合(即已浏览的点到起点的距离)

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 5e3 + 5, M = 2e5 + 5;
struct Edge{
	int to, val, ne;
}edge[M*2];
int head[N];
int cnt = 1;
void add_edge(int u, int v, int w){
	edge[cnt].to = v;
	edge[cnt].val= w;
	edge[cnt].ne = head[u];
	head[u] = cnt++;
}

int n,m;
int vis[N], dis[N];
typedef pair<int,int> pii;
priority_queue<pii, vector<pii>, greater<pii>>q;
void prim(){
	int num = 0; //边数 
	int sum = 0;
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	q.push({0,1});
	while(!q.empty()){
		int u = q.top().second, d = q.top().first;
		q.pop();
		if(vis[u]) continue;
		num++;
		sum += d;
		vis[u] = 1;
		for(int i = head[u]; i != 0; i = edge[i].ne){
			if(edge[i].val < dis[edge[i].to]){ //u到v的距离小于之前某个点到v的距离(和dij的区别就在这里)
			/*回顾一下dij,
			  if( dis[u] + edge[i]. val < dis[edge[i].to])
			  dis[edge[i].to] = dis[u] + edge[i]. val
			  很容易看出来,dij更新的是起点到目标点的距离,但是prim更新的是任意点到目标点的距离(因为prim只需要边最短就可以了) 
			*/
				dis[edge[i].to] = edge[i].val;
				q.push({dis[edge[i].to], edge[i].to}); 
			}
		}
	} 
	if(num == n) cout<<sum;
	else cout<<"orz"; 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i = 1; i <= m; i++){
		int u,v,w;
		cin>>u>>v>>w;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	prim();
	return 0;
}

总结

解决最大生成树也可以用一样的方法,不过把最小改成最大