1 条题解
-
0Guest LV 0
-
0
#include<bits/stdc++.h> using namespace std; int n,m,q[6000]; struct orz{ int x,y,z,save; }a[210000]; int sto(orz a,orz b) { return a.z < b.z; } int work(int x,int y) { while(q[q[x]] != q[x]) q[x] = q[q[x]]; while(q[q[y]] != q[y]) q[y] = q[q[y]]; if(q[x] == q[y]) return 1; else { q[q[y]] = q[x]; return 0; } } int main() { long long ans = 0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) q[i]=i; for(int i=1; i<=m; i++) { cin>>a[i].x>>a[i].y>>a[i].z; ans += a[i].z; } sort(a+1,a+m+1,sto); for(int i=1;i<=m;i++) { if(!work(a[i].x,a[i].y)) ans -= a[i].z; } cout << ans; return 0; }
- 1
信息
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 12
- 已通过
- 5
- 通过率
- 42%
- 上传者