洛谷3366
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=5010,maxm=200010; 5 int n,m,fa[maxn],tot=0,ans=0; 6 struct edge{int x,y,dis;}a[maxm]; 7 void read(int &k){ 8 k=0; int f=1; char c=getchar(); 9 while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 10 while ('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 11 k*=f; 12 } 13 bool cmp(edge a,edge b){return a.dis<b.dis;} 14 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} 15 int main(){ 16 read(n); read(m); 17 for (int i=1;i<=n;i++) fa[i]=i; 18 for (int i=1;i<=m;i++) read(a[i].x),read(a[i].y),read(a[i].dis); 19 sort(a+1,a+m+1,cmp); 20 for (int i=1,x,y;i<=m;i++){ 21 if (find(x=a[i].x)!=find(y=a[i].y)) fa[find(x)]=find(y),ans+=a[i].dis,tot++; 22 if (tot==n-1) break; 23 } 24 if (tot==n-1) printf("%d",ans); else printf("orz"); 25 }