暢通工程1863（并查集）（WA的思考）

暢通工程

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 47870    Accepted Submission(s): 21342

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

Input 測試輸入包含若幹測試用例。每個測試用例的第1行給出評估的道路條數 N、村莊數目M ( < 100 )；随後的 N

行對應村莊間道路的成本，每行給出一對正整數，分别是兩個村莊的編号，以及此兩村莊間道路的成本（也是正整數）。為簡單起見，村莊從1到M編号。當N為0時，全部輸入結束，相應的結果不要輸出。  

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

Sample Input

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

Sample Output

3 ?  

Source 注意一下判斷有點沒有聯通的方法：

可以用循環（雙重循環）周遊每一個點的的same函數是否為true

或者用一個循環放在K函數裡面看根節點是否大于1，大于1說明還有沒有聯通的點（因為最小生成樹全聯通的話隻有一個公共的根節點）

剛開始自己想錯就單純地判斷V和m-1的不等關系，但實際上比如就算輸入很多路（假設有3個村莊），但是輸入的總是第一個和第二個村莊的路，肯定是不行的。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std; 
const int maxn=20005;
int par[maxn];
int height[maxn];

struct edge
{
	int u;
	int v;
	int cost;
}es[maxn];

bool comp(const edge& e1,const edge&e2)
{
		return e1.cost<e2.cost;
}

void init(int n)
{
	for(int i=1;i<=n;i++)
	{
		par[i]=i;
		height[i]=0;
	}
}
int find(int x)
{
	if(par[x]==x)
	{
		return x;
	}
	else{
		return par[x]=find(par[x]);
	}
}
void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y) return;
	
	if(height[x]<height[y])
	{
		par[x]=y;
	}
	else
	{
		par[y]=x;
		if(height[x]==height[y])
		height[x]++;
	}
}
bool same(int x,int y)
{
	return find(x)==find(y);
}
int V,E;
int kruslkal()
{
	sort(es+1,es+E+1, comp);
	//init(V);/// 
	
	int res=0;
	for(int i=1;i<=E;i++)
	{
		edge e=es[i];
		if(!same(e.u,e.v))
		{
			unite(e.u,e.v);
			res+= e.cost;
		}	
	}
	int a=0;
	for(int i=1;i<=V;i++)
	{
		if(par[i]==i)
		a++;
	}
	if(a>1)
	return -1;
	else
	return res;	
}
int main(void)
{
	while(scanf("%d",&E)!=EOF)
	{
		if(E==0) break;
		scanf("%d", &V);
		memset(par,0,sizeof(par));memset(height,0,sizeof(height));memset(es,0,sizeof(es));
		
		init(V);
		
		for(int i=1;i<=E;i++)
		{
		 scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].cost); 
		}	
			int ans=kruslkal();
			if(ans==-1)
			printf("?\n");
			else printf("%d\n",ans);
		
		
	}
return 0;
}