大佬救命,58分kruskal
查看原帖
大佬救命,58分kruskal
854450
fufengyiye楼主2024/1/21 21:12
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

struct edge {
	int u, v, w;
	bool operator < (const edge& t)
	{
		return w < t.w;
	}
}e[200003];

int N, M;
const int inf = 10003;
int ans = 0;
int cnt = 0;
int fa[5003];

int find(int x)
{
	while (x != fa[x])
	{
		x = fa[x] = fa[fa[x]];
	}
	return x;
}

void Kru()
{
	for (int i = 1; i <= M; i++)
	{
		int x = find(e[i].u);
		int y = find(e[i].v);
		if (x != y)
		{
			fa[x] = y;
			ans += e[i].w;
			cnt++;
		}
		if (cnt == N- 1)
		{
			break;
		}
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int _u, _v, _w;
		cin >> _u >> _v >> _w;
		e[i].u = _u;
		e[i].v = _v;
		e[i].w = _w;
	}
	sort(e, e + M);
	for (int i = 1; i <= M; i++)
	{
		fa[i] = i;
	}
	Kru();
	if (cnt == N - 1)
		cout << ans << endl;
	else
		cout << "orz" << endl;
	return 0;
}
2024/1/21 21:12
加载中...