关注
这题克鲁斯卡尔就行
#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
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 不卡学历的大厂有哪些? #
8902次浏览 67人参与
# 顺丰求职进展汇总 #
52320次浏览 283人参与
# 除了主业以外,你还有哪些其他收入? #
3529次浏览 58人参与
# 职场新人体验 #
10115次浏览 105人参与
# 实习如何「偷」产出? #
15246次浏览 181人参与
# 实习打杂,要跑路吗 #
8481次浏览 102人参与
# 校园里的破防时刻 #
5066次浏览 54人参与
# 风评不好的公司,你会去吗? #
41496次浏览 278人参与
# 第一份工作应该选高薪还是热爱? #
77388次浏览 746人参与
# 社恐入职新公司如何融入团队 #
10142次浏览 62人参与
# 一人推荐一个值得去的通信/硬件公司 #
188289次浏览 1867人参与
# 学历贬值真的很严重吗? #
27761次浏览 187人参与
# 我的工作日记 #
121142次浏览 1432人参与
# 腾讯音乐求职进展汇总 #
96413次浏览 559人参与
# 你觉得早上几点上班合适? #
74481次浏览 309人参与
# 毕业旅行去哪玩儿 #
13791次浏览 135人参与
# 百度秋招提前批进度 #
108754次浏览 1151人参与
# 考研可以缓解求职焦虑吗 #
52938次浏览 471人参与
# 双非能在秋招上岸吗? #
223934次浏览 1184人参与
# 秋招OC许愿 #
325391次浏览 2446人参与