14 solutions
-
-5
注意:
- 不要把洛谷AC代码移过来,注意数据范围
- 不要用
int
!!
不要复制下面的代码
#include<bits/stdc++.h> using namespace std; int n,m; struct Edge{ int u,v; long long len; }e[2000₁0]; bool cmp(Edge a,Edge b){ return a.len<=b.len; } int fa[100010]; void init(){ for(int i=1;i<=n;i++)fa[i]=i; } int get(int x){ if(fa[x]==x)return x; return fa[x]=get(fa[x]); } void merge(int x,int y){ x=get(x); y=get(y); if(x!=y){ fa[x]=y; } } int kruskal(int n,int m){ long long sum=0; init(); sort(e,e+m,cmp); for(int i=0;i<m;i++){ int fu=get(e[i].u); int fv=get(e[i].v); if(fu!=fv){ fa[fv]=fu; sum+=e[i].len; } } return sum; } int mian(){ cin>>n>>m; for(int i=0;i<m;++i)cin>>e[i].u>>e[i].v>>e[i].len; cout<<kruskal(n,m)<<endl; return 0; }
Information
- ID
- 91
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- # Submissions
- 857
- Accepted
- 279
- Uploaded By