POJ 1258 Agri-Net（裸最小生成树）

**链接：****传送门！ **

题意：一个裸最小生成树，采用Kruskal。

/*************************************************************************

    > File Name: poj1258.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年06月19日 星期一 18时20分30秒

 ************************************************************************/

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int MAX_N = 110;

struct edge{

	int from , to , cost;

}E[MAX_N*MAX_N];

int par[MAX_N];

void init_union_find_set()	{ for(int i = 0 ; i < MAX_N ; i++) par[i] = i; }

int  find(int x)			{ return x == par[x] ? x : par[x] = find(par[x]); }

bool same(int x,int y)		{ return find(x) == find(y); }

void union_data(int x,int y){ x = find(x);	y = find(y);	if(x!=y) par[y] = x; }

bool cmp(edge a,edge b){

	return a.cost < b.cost;

}

int  Kruskal(int n , int size){

	init_union_find_set();

	sort(E,E+size,cmp);

	int ret = 0;

	for(int i = 0 ; i < size ; i++){

		if( !same(E[i].from,E[i].to) ){

			union_data(E[i].from,E[i].to);

			ret += E[i].cost;

		}

	}

	return ret;

}

int main(){

	int n , cost;

	while(~scanf("%d",&n)){

		int cnt = 0;

		memset(E,0,sizeof(E));

		for(int i = 0 ; i < n ; i++){

			for(int j = 0 ; j < n ; j++){

				scanf("%d",&cost);

				if(cost){	E[cnt].from = i , E[cnt].to = j , E[cnt++].cost = cost;  }

			}

		}

		int ret = Kruskal(n,cnt);

		printf("%d\n",ret);

	}

	return 0;

}

巴特西

POJ 1258 Agri-Net（裸最小生成树）

最新文章

热门文章

巴特西

POJ 1258 Agri-Net（ 裸最小生成树 ）

最新文章

热门文章

POJ 1258 Agri-Net（裸最小生成树）