这题克鲁斯卡尔就行 #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

相关推荐

在等offer的火锅...:我去履历这么好,都找不到工作吗?
点赞 评论 收藏
分享
07-21 18:43
门头沟学院 Java
是暑期都招满了吗
ANEOY:今年感觉真是后端地狱级难度了,从暑期就是这样,前端需求非常大
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务