1 条题解
-
4
#include<bits/stdc++.h> using namespace std; const int N=2e3+5; const int M=3e3+5; int n,m,fa[N],cnt,ans; struct node{ int x,y,w; }edge[M]; bool cmp(node a,node b){ return a.w<b.w; } int find(int x){ if(fa[x]==x){ return x; } return fa[x]=find(fa[x]); } void unionn(int x,int y){ int fx=find(x); int fy=find(y); fa[fx]=fy; return; } void kruskal(){ for(int i=1;i<=n;i++){ fa[i]=i; } sort(edge+1,edge+m+1,cmp); for(int i=1;i<=m;i++){ int x=edge[i].x; int y=edge[i].y; if(find(x)!=find(y)){ unionn(x,y); ans+=edge[i].w; cnt++; } if(cnt==n-1){ return; } } return; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>edge[i].x>>edge[i].y>>edge[i].w; } kruskal(); cout<<ans; return 0; }
信息
- ID
- 2
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 8
- 已通过
- 8
- 上传者