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.

Delete this entry (admin only).