題目1024：暢通工程

題目描述：

    省政府“暢通工程”的目标是使全省任何兩個村莊間都可以實作公路交通（但不一定有直接的公路相連，隻要能間接通過公路可達即可）。經過調查評估，得到的統計表中列出了有可能建設公路的若幹條道路的成本。現請你編寫程式，計算出全省暢通需要的最低成本。

輸入：

    測試輸入包含若幹測試用例。每個測試用例的第1行給出評估的道路條數 N、村莊數目M (N, M < =100 )；随後的 N 行對應村莊間道路的成本，每行給出一對正整數，分别是兩個村莊的編号，以及此兩村莊間道路的成本（也是正整數）。為簡單起見，村莊從1到M編号。當N為0時，全部輸入結束，相應的結果不要輸出。

輸出：

    對每個測試用例，在1行裡輸出全省暢通需要的最低成本。若統計資料不足以保證暢通，則輸出“?”。

樣例輸入：

3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100      

樣例輸出：

3
?      

AC代碼：

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;
int Tree[101];
struct Way
{
	int v1;
	int v2;
	int cost;
};
bool cmp(Way a,Way b)
{
	return a.cost < b.cost;
}
int findRoot(int x)
{
	if(Tree[x] == -1) 
	{
		return x;
	}
	else
	{
		int tmp = findRoot(Tree[x]);
		Tree[x] = tmp;
		return tmp;
	}
}
struct Way way[101];
int main()
{
	int N,M,i;
	int sum;
	int count;
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		if(N == 0) break;
		sum = 0;
		count = 0;
		memset(Tree,-1,sizeof(int)*101);
		for(i = 1; i <= N; i++)
		{
			scanf("%d%d%d",&way[i].v1,&way[i].v2,&way[i].cost);
		}
		// 将數組按從小到大排序
		sort(way+1,way+N+1,cmp);   //  從way+1開始位置，共N個元素
		for(i = 1;i <= N; i++)
		{
			int x = findRoot(way[i].v1);
			int y = findRoot(way[i].v2);
			if(x!=y)    // 不存在回路就添加進來
			{
				Tree[x] = y;
				sum += way[i].cost;  
			}
		}
		for(i = 1; i <= M;i++)
		{
			if(Tree[i] == -1)    //若有2個或2個以上的結點的父節點還是-1，說明還存在孤立的點或路徑
				count++;
		}
		if(count > 1)
			printf("%s\n","?");
		else if(count == 1)
			printf("%d\n",sum);
	}
	
	return 0;
}
           

筆記：還是用Kruskal算法求最小生成樹，把路徑換成了成本而已，另外添加了判斷最小生成樹是否存在的判斷，不得不說九度OJ真會玩，暢通工程都出來好幾個題目了，這個題目此番WA了很多次的重要原因是沒有徹底弄清sort函數的使用，當對數組不是從第一個元素開始時排序時沒弄明白。