专栏文章

P3366题解

P3366题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip44rd7
此快照首次捕获于
2025/12/03 05:51
3 个月前
此快照最后确认于
2025/12/03 05:51
3 个月前
查看原文

前言

需要掌握并查集等前置知识。

思路

最小生成树

最小生成树是指在无向连通图中边权和最小的树。

Kruskal

我们采用Kruskal实现。
如图:
每次选出边权最小的一边,将该边所连接的两点放入一个并查集中。如果两点已经连通(在同一个并查集中)则不进行操作。

证明(贪心)

令树 T1T_1T2T_2 是两棵最小生成树则通过它们之间边权最小的边将它们合并为一棵树 TT,则 TT 也一定是一棵最小生成树。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
//#define int long long
struct NODE
{
	int z,x,y;
	bool operator < (const NODE t) const
	{
		return z<t.z;
	}
}; 
int a[5005];
NODE b[200005];
//压缩路径
int find(int x)
{
	if(!a[x]) return x;
	return a[x] = find(a[x]);
}
//加入
void add(int x,int y)
{
	a[find(x)] = find(y);
}
//是否连通
bool isbrother(int x,int y)
{
	return find(x)==find(y);
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>b[i].x>>b[i].y>>b[i].z;
	//按边权排序
	sort(b+1,b+1+m);
	int ans = 0;
	for(int i=1;i<=m;i++)
	{
		//不连通就放入同个并查集
		if(!isbrother(b[i].x,b[i].y))
		{
			ans += b[i].z;
			add(b[i].x,b[i].y);
		}
	}
	for(int i=2;i<=n;i++)
	{
		//如果连通的话再压缩路径之后任意两点一定连通
		if(!isbrother(1,i))
		{
			cout<<"orz";
			return 0;
		}
	}
	cout<<ans;
	return 0;
}

后记

部分参考于OI Wiki

评论

0 条评论,欢迎与作者交流。

正在加载评论...