AC

打倒诶嘿抢榜一  •  4个月前


include <bits/stdc++.h>

define M 2000005

define N 100005

using namespace std; int n, m; long long ans; int cnt = 1; int fa[N];//定义父节点

struct eage {

int from, to, w;//from我从哪来,to到哪去呢,w我的权值是干嘛的呢

} e[M];

bool mpt(eage a, eage b) {

return a.w < b.w;

}//排序规则

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

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

} //存储边 void init() {

for (int i = 0; i < N; i++) {
	fa[i] = i;
}

} //初始化父节点 int find(int x) {

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

} //并查集 查 void Union(int x, int y) {

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

} //并查集 并 void kuruskal() {

int k = 0;
sort(e + 1, e + 1 + m, mpt);//排序
for (int i = 1; i <= m; i++) {
	if (find(e[i].from) != find(e[i].to)) {
		Union(e[i].from, e[i].to);
		k++;//边+1
		ans += e[i].w;//权值累加
	}
	if (k == n - 1) {
		cout << ans;
		break;
	}//判断是否构成一棵树
}
if (k != n - 1) {
	cout << "orz";
}

}

int main() {

init();
cin >> n >> m;
for (int i = 1; i <= m; i++) {
	int u, v, w;
	cin >> u >> v >> w;
	add(u, v, w);
}
kuruskal();
return 0;

}


评论:

请先登录,才能进行评论