# Demo entry 6343523

111

Submitted by 11 on Jan 10, 2017 at 08:51
Language: C++. Code size: 1.1 kB.

```#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=105;
const int inf=0x3f3f3f3f;
typedef struct{
int x,y,s;
}edge;
edge e[maxn*maxn];
int n,m,f[maxn];
bool cmp(edge u,edge v){
return u.s < v.s;
}
void init(){
for(int i=1;i<=n;i++)
f[i]=i;
}
int find(int x){
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
bool Union(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
f[fx]=fy;
return true;
}
return false;
}
int kruskal(){
int count=0,mst=0;
sort(e+1,e+m+1,cmp);
printf("水渠连接说明：\n");
for(int i=1;i<=m;i++){
if(Union(e[i].x,e[i].y)){
mst+=e[i].s;
count++;
printf("  麦田%d---麦田%d\n",e[i].x,e[i].y);
}
if(count==n-1)
break;
}
return mst;
}
int main(){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].s);
int mst=kruskal();
printf("最少费用：%d\n",mst);
return 0;
}
```

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.