最小生成树

敖丙  •  2个月前


include <bits/stdc++.h>

using namespace std;

define M 2000005

define N 100005

int fa[N]; int n, m, cnt = 1; long long ans = 0;

struct edge {

int from, to, w;

} e[M];

void init() {

for (int x = 0; x < N; x++)
	fa[x] = x;

}

bool cmp(edge a, edge b) {

return a.w < b.w;

}

void addedge(int u, int v, int w) {

e[cnt].from = u;
e[cnt].to = v;
e[cnt].w = w;
cnt++;

}

int find(int x) {

if (fa[x] != x)
	return fa[x] = find(fa[x]);
return fa[x];

}

void uni(int x, int y) {

x = find(x);
y = find(y);
if (x != y)
	fa[x] = y;

}

void kruskal() {

int k = 0;
sort(e + 1, e + 1 + m, cmp);
for (int x = 1; x <= m; x++) {
	if (find(e[x].from) != find(e[x].to)) {
		uni(e[x].from, e[x].to);
		k++;
		ans += e[x].w;
	}
	if (k == n - 1) {
		cout << ans;
		break;
	}
}
if (k != n - 1) {
	cout << "orz";
}

}

int main() {

init();
cin >> n >> m;
for (int x = 1; x <= m; x++) {
	int u, v, w;
	cin >> u >> v >> w;
	addedge(u, v, w);
}
kruskal();
return 0;

}


评论:

请先登录,才能进行评论