洛谷P3366 【模板】最小生成树
#include<bits/stdc++.h> #include<ext/rope> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)); #define ll long long int const int INF = 0x3f3f3f3f; int pre[5005]; int n,m; struct node1 { int x,y,w; }node[200020]; void init() { for(int i=1;i<=n;++i) pre[i]=i; } bool cmp(node1 x,node1 y) { return x.w<y.w; } int Find(int son) { int deson,dad; deson=son; while(son!=pre[son]) son=pre[son]; while(deson!=pre[deson]) { dad=pre[deson]; pre[deson]=son; deson=dad; } return son; } void kruskal() { sort(node,node+m,cmp); int sum=0,js=0,dad1,dad2; for(int i=0;i<m;++i) { dad1=Find(node[i].x); dad2=Find(node[i].y); if(dad1!=dad2) { sum+=node[i].w; pre[dad1]=dad2; ++js; if(js==n-1) break; } } if(js==n-1) printf("%d\n",sum); else printf("orz\n"); } int main() { scanf("%d%d",&n,&m); init(); for(int i=0;i<m;++i) { scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w); } kruskal(); return 0; }