欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P3366 【模板】最小生成树(C++_(Prim算法_链式向前星)/(Kruskal算法_并查集))

程序员文章站 2024-02-29 12:44:04
...

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。

输入格式

第一行包含两个整数 N,M,表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi,Yi,ZiX_i,Y_i,Z_i​,表示有一条长度为 ZiZ_i​ 的无向边连接结点 Xi,YiX_i,Y_i

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

7

说明/提示

数据规模:

对于 20%20\%的数据,N5N\le 5M20M\le 20

对于 40%40\% 的数据,N50N\le 50M2500M\le 2500

对于 70%70\% 的数据,N500N\le 500M104M\le 10^4

对于 100%100\%的数据:1N50001\le N\le 50001M2×1051\le M\le 2\times 10^5

样例解释:

P3366 【模板】最小生成树(C++_(Prim算法_链式向前星)/(Kruskal算法_并查集))
所以最小生成树的总边权为 2+2+3=72+2+3=7

思路

关于链式向前星可以参考这篇博客图的存储模式——链式向前星,链式向前星是一种逆序存储后输入的先遍历,具体的过程看过那篇博客后应该就懂了,这个其实也有模板的,精华就是add函数,链式向前星模板如下:

void add(int u, int v, int w)//链式向前星存储(逆向存储)
{
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}

下面就是Prim算法,就像是大佬说的那样Prim算法其实和最短路中的dijkstra很像,不断地贪心地向外扩充…
P3366 【模板】最小生成树(C++_(Prim算法_链式向前星)/(Kruskal算法_并查集))图片转自最小生成树算法(有兴趣也可以康康这个博客,我就是从dalao这里学到的啦~~~)

Code1(Prim)

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f
class node
{
public:
	int to, next, w;
}edge[400010];
int n, m, head[200010], dis[200010], cnt = 0, ans = 0, sum = 0, vis[200010], now = 1;
void add(int u, int v, int w)//链式向前星存储(逆向存储)
{
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
int prim()
{
	memset(dis, INF, sizeof(dis));
	for (int i = head[1]; i; i = edge[i].next)
		dis[edge[i].to] = min(dis[edge[i].to], edge[i].w);//若两点之间出现多条边,只取最短的那条(图的重边)
	while (++sum < n)//一张图的边比节点少一
	{
		int minn = INF;
		vis[now] = 1;
		for(int i=1;i<=n;i++)
			if (!vis[i] && minn > dis[i])
			{
				minn = dis[i];
				now = i;
			}
		ans += minn;
		for (int i = head[now]; i; i = edge[i].next)
			if(dis[edge[i].to]> edge[i].w&&!vis[edge[i].to])//一个节点不能走两遍
				dis[edge[i].to] = edge[i].w;
	}
	return ans;
}
int main()
{
	memset(head, 0, sizeof(head));
	int u, v, w;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	cout << prim();
	return 0;
}

Code2(Kruskal)

Kruskal算法的思想比Prin好理解一些。先把边按照权值进行排序,用贪心的思想优先选取权值较小的边,并依次连接,若出现环则跳过此边(用并查集来判断是否存在环)继续搜,直到已经使用的边的数量比总点数少一即可。
#include<bits/stdc++.h>
using namespace std;
class node
{
public:
	int u, v, w;
}edge[400010];
int n, m, f[5010], ans = 0, num = 0, t1, t2;
bool cmp(node a, node b){
	return a.w < b.w;
}
int find(int k)
{
	if (f[k] == k)
		return k;
	return f[k] = find(f[k]);
}
void kruskal()
{
	sort(edge + 1, edge + 1 + m, cmp);
	for (int i = 1; i <= m; i++)
	{
		t1 = find(edge[i].u);
		t2 = find(edge[i].v);
		if (t1 == t2)
			continue;
		ans += edge[i].w;
		f[t1] = t2;
		if (++num == n - 1)//最小生成树的边比节点少一
			break;
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		f[i] = i;//初始化并查集
	for (int i = 1; i <= m; i++)
		cin >> edge[i].u >> edge[i].v >> edge[i].w;
	kruskal();
	cout << ans;
	return 0;
}
相关标签: 洛谷刷题