HDU 1879 繼續暢通工程

/*
題目大意：求最少的資金，但裡面包括了已經修好的路
解題思路：將已修的路全部去除（但要連接他們的父結點，並只剩下一個結點），留下未修的，將未修的排序，找出資金最少的，直到父結點是一樣的
難點詳解：已修路和未修路父結點的統一
關鍵點：如何將他們統一
解題人：lingnichong
解題時間：2014-08-19 23:38:57
解題體會：思路清晰，還要去做
*/

繼續暢通工程

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13985 Accepted Submission(s): 6084

Problem Description 省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。現得到城鎮道路統計表，表中列出了任意兩城鎮間修建道路的費用，以及該道路是否已經修通的狀態。現請你編寫程序，計算出全省暢通需要的最低成本。

Input 測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數目N ( 1< N < 100 )；隨後的 N(N-1)/2 行對應村莊間道路的成本及修建狀態，每行給4個正整數，分別是兩個村莊的編號（從1編號到N），此兩村莊間道路的成本，以及修建狀態：1表示已建，0表示未建。

當N為0時輸入結束。
Output 每個測試用例的輸出占一行，輸出全省暢通需要的最低成本。
Sample Input

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

Sample Output

3
1
0

#include
#include
using namespace std;

int father[110];

struct st
{
	int u,v,w,build;
}some[10000];

int cmp(st x,st y)//排序，將沒修過的路放在上方，再對沒修路的價格進行排序
{
	if(x.build != y.build)  
		return x.build < y.build;
	return x.w < y.w;
}

int find(int x)//找出父代結點
{
	return x==father[x]?x:father[x]=find(father[x]);
}

void join(int x,int y)//此處為空，只為將修過路的父節點統一到一個結點
{
	int fa=find(x),fb=find(y);
	if(fa != fb)
		father[fa] = fb;
}

int main()
{
	int i,j;
	int n,m;
	int sum;
	while(~scanf("%d",&n),n)
	{
		m=n*(n-1)/2;
		sum=0;
		for(i=1;i<=n;i++)//要先賦值為自己為父結點，方便後面程序的運行
			father[i]=i;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d%d",&some[i].u,&some[i].v,&some[i].w,&some[i].build);
			if(some[i].build==1)//找到已修路的統一的結點
			join(some[i].u,some[i].v);
		}
		sort(some+1,some+m+1,cmp);
		for(i=1;i<=m;i++)
		{
			int x,y;
			x=find(some[i].u);
			y=find(some[i].v);
			if(x != y && !some[i].build)//要使資金最少，則兩個村莊的父結點是不一樣的並且是未建造
			{
				sum+=some[i].w;
				father[x]=y;
			}
		}
		printf("%d\n",sum);
		
	}
	return 0;
}