关注
这题克鲁斯卡尔就行
#include<bits/stdc++.h>
using namespace std;
vector<int> father;
int find(int x){
return father[x] == x ? x : father[x] = find(father[x]);
}
bool cmp(const vector<int>&; a, const vector<int>&; b){
return a[2] < b[2];
}
int main(){
int n, m;
cin>>n>>m;
father = vector<int>(n + 1);
for(int i = 1; i <= n; i++) father[i] = i;
vector<vector<int>> edges(m, vector<int>(3));
for(int i = 0; i < 3; i++){
for(int j = 0; j < m; j++)
cin>>edges[j][i];
}
sort(edges.begin(), edges.end(), cmp);
int ans = 0;
for(int i = 0; i < m; i++){
int f1 = find(edges[i][0]), f2 = find(edges[i][1]);
if(f1 == f2) continue;
ans += edges[i][2];
int ff = min(f1, f2);
father[f1] = father[f2] = ff;
}
cout<<ans<<endl;
return 0;
}
查看原帖
3 1
相关推荐
06-21 00:26
无锡高等师范学校 算法工程师 风行者666:26届的现在都找不到实习,别说你27了。还有我主观感觉你这个项目描述怎么一股ai味

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 哪些公司开提前批了? #
28072次浏览 268人参与
# 入职以后才知道的校招谎言 #
88747次浏览 583人参与
# 风评不好的公司,你会去吗? #
63737次浏览 450人参与
# 华子oc时间线 #
1244673次浏览 6487人参与
# 哪些公司校招卡第一学历 #
70627次浏览 280人参与
# 校招第一份工作你干了多久? #
95328次浏览 423人参与
# 实习如何「偷」产出? #
53172次浏览 1358人参与
# 除了主业以外,你还有哪些其他收入? #
12711次浏览 202人参与
# 不卡学历的大厂有哪些? #
30825次浏览 233人参与
# 机械人,你的第一份感谢信是谁给的 #
30628次浏览 310人参与
# 校招阶段,学历VS技术哪个更重要? #
18344次浏览 188人参与
# 职场新人体验 #
27416次浏览 251人参与
# 研究所笔面经互助 #
78608次浏览 483人参与
# 工作丧失热情的瞬间 #
294186次浏览 2372人参与
# 腾讯音乐求职进展汇总 #
98300次浏览 571人参与
# 你的秋招第一场笔试是哪家 #
148338次浏览 1485人参与
# 社恐入职新公司如何融入团队 #
12105次浏览 63人参与
# 华为开奖那些事 #
4094927次浏览 24608人参与
# 校园里的破防时刻 #
12132次浏览 128人参与
# Offer比较,你最看重什么? #
191926次浏览 1308人参与