【C++】图论|生成树问题(MST)模板

Toms Project • • 信息技术 • 13 阅读

顾名思义：即是对一个连通图，删去一定边，使得剩下的部分成为一棵树（无环）。求剩下的树的最小边权和。

题目：P3366 【模板】最小生成树（https://www.luogu.com.cn/problem/P3366）

有两种主要的算法，分别基于对边和对点操作得到。

Kruskal 算法

基于并查集，对边排序操作的贪心算法。

C++
// MST Kruskal O(nlog n)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> root;
int ans = 0, cnt = 0;

struct edge
{
	int u, v, w;
	bool operator < (const edge& e) const
	{
		return w < e.w;
	}
};
vector<edge> edg;

void init(int n)
{
	root.resize(n + 1);
	for (int i = 1; i <= n; i++) root[i] = i;
}

int find(int x)
{
	if (x != root[x])
	{
		root[x] = find(root[x]);
	}
	return root[x];
}

bool kruskal(int n)
{
	init(n);
	sort(edg.begin(), edg.end());
	for (auto& i : edg)
	{
		int x = find(i.u), y = find(i.v);
		if (x != y)
		{
			root[x] = y;
			ans += i.w;
			cnt++;
		}
	}
	return cnt == n - 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	edg.resize(m);
	for (auto& i : edg)
	{
		cin >> i.u >> i.v >> i.w;
	}
	if (!kruskal(n)) cout << "orz" << endl;
	else cout << ans << endl;
	return 0;
}

Prim 算法

思想和写法都和最短路算法 Dijkstra 算法十分相似。每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。

根据点的不同维护方式（暴力和堆优化）分为两种时间复杂度的版本。

O(N^2) 版本

C++
// MST Prim O(n2)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <climits>

using namespace std;
using pii = pair<int, int>;
vector<vector<pii>> edg;
vector<bool> vis;
vector<int> dis;
int ans = 0, cnt = 0;

bool prim(int n)
{
	vis.resize(n + 1);
	dis.resize(n + 1, INT_MAX);
	dis[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		int u = 0;
		for (int j = 1; j <= n; j++)
		{
			if (!vis[j] && dis[j] < dis[u]) u = j;
		}
		ans += dis[u];
		vis[u] = 1;
		if (dis[u] != INT_MAX) cnt++;
		for (auto& j : edg[u])
		{
			if (dis[j.first] > j.second) dis[j.first] = j.second;
		}
	}
	return cnt == n;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, c;
	cin >> n >> m;
	edg.resize(n + 1);
	while (m--)
	{
		cin >> a >> b >> c;
		edg[a].emplace_back(b, c);
		edg[b].emplace_back(a, c);
	}
	if (!prim(n)) cout << "orz" << endl;
	else cout << ans << endl;
	return 0;
}

O(nlog n) 版本

C++
// MST Prim O(nlog n)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <climits>

using namespace std;
using pii = pair<int, int>;
vector<vector<pii>> edg;
vector<bool> vis;
vector<int> dis;
int ans = 0, cnt = 0;

struct point
{
	int u, w;
	bool operator < (const point& p) const
	{
		return w > p.w;
	}
};

bool prim(int n)
{
	priority_queue<point, vector<point>, less<point>> q;
	dis.resize(n + 1, INT_MAX);
	vis.resize(n + 1);
	dis[1] = 0;
	q.emplace(point{ 1,dis[1] });
	while (!q.empty())
	{
		auto top = q.top();
		q.pop();
		if (vis[top.u]) continue;
		vis[top.u] = 1;
		ans += dis[top.u];
		cnt++;
		for (auto& i : edg[top.u])
		{
			if (dis[i.first] > i.second)
			{
				dis[i.first] = i.second;
				q.emplace(point{ i.first,dis[i.first] });
			}
		}
	}
	return cnt == n;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, c;
	cin >> n >> m;
	edg.resize(n + 1);
	while (m--)
	{
		cin >> a >> b >> c;
		edg[a].emplace_back(b, c);
		edg[b].emplace_back(a, c);
	}
	if (!prim(n)) cout << "orz" << endl;
	else cout << ans << endl;
	return 0;
}

目前有关MST就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。

版权声明：
作者：Toms Project
链接：https://blog.projectoms.com/pages/1637.html
来源：Toms Project 官方博客
文章版权归作者所有，未经允许请勿转载。

THE END
分享
二维码
打赏
< <上一篇
下一篇>>
文章目录
关闭
目 录