求条
  • 板块灌水区
  • 楼主Henly_Z
  • 当前回复10
  • 已保存回复11
  • 发布时间2024/8/1 09:11
  • 上次更新2024/8/1 10:33:33
查看原帖
求条
683212
Henly_Z楼主2024/8/1 09:11

P1967RE了3个点

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 100000+5;
struct Node{
	int u , v , w ;
}e[N];
int n , m , f[N] , cnt , sum;
int find(int x){
	return f[x] == x ? f[x] : find(f[x]);
}
bool cmp(Node x, Node y)
{
	return x.w < y.w;
}
bool merge(int x , int y)
{
	x = find(x) , y = find(y);
	if(x == y)
	{
		return false;
	}
	f[x] = y;
	return true;
}
int main()
{
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++)
	{
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	for(int i = 1 ; i <= m ; i++)
	{
		f[i] = i;
	}
	sort(e , e + m,cmp);
	for(int i = 0 ; i < m ; i++)
	{
		int u = e[i].u ; int v = e[i].v ; int w = e[i].w;
		if(merge(u,v)){
			cnt++;
			sum += w;
		}
	}
	if(cnt == n - 1)
	{
		cout << sum << "\n";
	}
	else
	{
		cout << "orz";
	}
} 
2024/8/1 09:11
加载中...