還是暢通工程

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 22226 Accepted Submission(s): 9939


Problem Description 某省調查鄉村交通狀況，得到的統計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可），並要求鋪設的公路總長度為最小。請計算最小的公路總長度。

Input 測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數目N ( < 100 )；隨後的N(N-1)/2行對應村莊間的距離，每行給出一對正整數，分別是兩個村莊的編號，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號。
當N為0時，輸入結束，該用例不被處理。

Output 對每個測試用例，在1行裡輸出最小的公路總長度。

Sample Input

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

Sample Output

3
5

HintHint 
Huge input, scanf is recommended.

Prim(鄰接矩陣, 134ms):

#include 
#include 
#define N 100

int n;
int map[N][N], low[N];
bool vis[N];

void Init(){
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= n; i ++){
		low[i] = 0xfffffff;
		for(int j = 1; j <= n; j ++){
			map[i][j] = 0xfffffff;
		}
	}
}

int Prim(int choose){
	low[choose] = 0;
	vis[choose] = 1;
	for(int i = 1; i <= n; i ++){
		low[i] = map[choose][i];
	}
	
	int ans = 0;
	for(int j = 1; j < n; j ++){
		int Min = 0xfffffff;
		for(int i = 1; i <= n; i ++){
			if(!vis[i] && Min > low[i]){
				Min = low[i];
				choose = i;
			}
		}
		vis[choose] = 1;
		ans += Min;
		for(int i = 1; i <= n; i ++){
			if(!vis[i] && low[i] > map[choose][i]){
				low[i] = map[choose][i];
			}
		}
	}
	
	return ans;
}

int main()
{
	int start, end, len;
	while(scanf("%d", &n), n){
		Init();
		for(int i = 0; i < n * (n - 1) / 2; i ++){
			scanf("%d%d%d", &start, &end, &len);
			if(map[start][end] > len){
				map[start][end] = map[end][start] = len;
			}
		}
		
		int ans = Prim(1);
		
		printf("%d\n", ans);
	}
	
	return 0;
}

Prim(鄰接表, 250ms):

#include 
#include 
#include 
#define N 100

using namespace std;

struct Node{
	int next;
	int len;
};

int n;
int low[N];
bool vis[N];
vectorq[N];

void Init(){
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= n; i ++){
		low[i] = 0xfffffff;
		q[i].clear();
	}
}

int Prim(int choose){
	low[choose] = 0;
	vis[choose] = 1;
	for(int i = 0; i < q[choose].size(); i ++){
		int next = q[choose].at(i).next;
		int len = q[choose].at(i).len;
		low[next] = len;
	}
	
	int ans = 0;
	for(int j = 1; j < n; j ++){
		int Min = 0xfffffff;
		for(int i = 1; i <= n; i ++){
			if(!vis[i] && Min > low[i]){
				Min = low[i];
				choose = i;
			}
		}
		vis[choose] = 1;
		ans += Min;
		for(int i = 0; i < q[choose].size(); i ++){
			int next = q[choose].at(i).next;
			int len = q[choose].at(i).len;
			if(!vis[next] && low[next] > len){
				low[next] = len;
			}
		}
	}
	
	return ans;
}

int main()
{
	Node nw;
	int start, end, len;
	while(scanf("%d", &n), n){
		Init();
		for(int i = 0; i < n * (n - 1) / 2; i ++){
			scanf("%d%d%d", &start, &end, &len);
			nw.next = end;
			nw.len = len;
			q[start].push_back(nw);
			nw.next = start;
			q[end].push_back(nw);
		}
		
		int ans = Prim(1);
		
		printf("%d\n", ans);
	}
	
	return 0;
}

Kruskal(鄰接表, 296ms):

#include 
#include 
#define N 110

using namespace std;

struct Node{
	int start;
	int end;
	int len;
	friend bool operator < (const Node& a, const Node& b){
		return a.len > b.len;
	}
};

int n;
priority_queueq;
int Father[N];

void Init(){
	for(int i = 0; i <= n; i ++){
		Father[i] = i;
	}
}

int GetFather(int cur){
	return Father[cur] == cur ? cur : Father[cur] = GetFather(Father[cur]);
}

bool Join(int start, int end){
	int root1 = GetFather(start);
	int root2 = GetFather(end);
	
	if(root1 == root2){
		return 0;
	}
	else{
		Father[root1] = root2;
		return 1;
	}
}

int Kruskal(){
	int ans = 0;
	while(!q.empty()){
		Node cur = q.top();
		q.pop();
		
		if(Join(cur.start, cur.end)){
			ans += cur.len;
		}
	}
	
	return ans;
}

int main()
{
	Node nw;
	int start, end, len;
	while(scanf("%d", &n), n){
		Init();
		for(int i = 0; i < n * (n - 1) / 2; i ++){
			scanf("%d%d%d", &start, &end, &len);
			nw.start = start;
			nw.end = end;
			nw.len = len;
			q.push(nw);
		}
		
		int ans = Kruskal();
		
		printf("%d\n", ans);
	}
	
	return 0;
}