九度OJ 1024 畅通工程 -- 并查集、贪心算法(最小生成树)

题目地址：http://ac.jobdu.com/problem.php?pid=1024

题目描述：: 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

输入：: 测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

输出：: 对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

样例输入：

样例输出：

3

?

来源：: 2007年浙江大学计算机及软件工程研究生机试真题

#include <stdio.h>

#include <stdlib.h>

typedef struct node{

	int start;

	int end;

	int weight;

}Node;

int father[101];

int rank[101];

void Make_Set (int M){

	int i;

	for (i=1; i<=M; ++i){

		father[i] = i;

		rank[i] = 0;

	}

}

int Find_Set (int x){

	if (x != father[x]){

		father[x] = Find_Set (father[x]);

	}

	return father[x];

}

int Union (int x, int y){

	x = Find_Set (x);

	y = Find_Set (y);

	if (x == y)

		return 0;

	if (rank[x] > rank[y]){

		father[y] = x;

		rank[x] += rank[y];

	}

	else{

		if (rank[x] == rank[y])

			++rank[y];

		father[x] = y;

	}

	return 1;

}

int compare (const void * p, const void * q){

	Node * p1 = (Node *)p;

	Node * q1 = (Node *)q;

	return p1->weight - q1->weight;

}

int main(void){

	int N, M;

	Node road[5000];

	int i;

	int cnt;

	int ans;

	while (scanf ("%d%d", &N, &M) != EOF){

		if (N == 0)

			break;

		//scanf ("%d", &M);

		for (i=0; i<N; ++i){

			scanf ("%d%d%d", &road[i].start, &road[i].end, &road[i].weight);

		}

		qsort (road, N, sizeof(Node), compare);

		Make_Set (M);

		ans = 0;

		cnt = 0;

		for (i=0; i<N; ++i){

			if (cnt == M - 1)

				break;

			if (Union (road[i].start, road[i].end)){

				++cnt;

				ans += road[i].weight;

			}

		}

		if (cnt == M - 1){

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

		}

		else{

			printf ("?\n");

		}

	}

	return 0;

}

九度OJ上相似的题目：http://ac.jobdu.com/problem.php?pid=1347，CODE代码片

巴特西

九度OJ 1024 畅通工程 -- 并查集、贪心算法(最小生成树)

最新文章

热门文章