最小生成樹典型例題 POJ2485 Highways

原題連結：POJ2485 Highways

樣例輸入

1

3

0 990 692

990 0 179

692 179 0

樣例輸出

692

Hint

Huge input,scanf is recommended.

描述 ：有個城市叫做H市。其中有很多個村莊，村莊之間通信基本靠吼，交通基本靠走，很不友善。

這個市長知道了這個情況，為了替市民着想，決定修建高鐵。每修建一米花費1美元。

現在市長請了最著名的工程師來修建高鐵，自然這個工程師會讓修建高鐵的費用最少。

不幸的是，在修建了高鐵之後就病逝了。現在市長希望知道在修建完成的這些高鐵路中最長的一段高鐵路花費了多少美元，

他請你來幫助他，如果你計算正确，市長将會送你一輛蘭博基尼。

輸入：

第一行一個數T，表示接下來有多少組資料。

接下來每組測試資料的第一行有一個數N（3<=N<=500），表示村莊數目。

然後是一個二維數組，第i行第j清單示第i個村莊到第j個村莊的距離。

輸出：

隻有一個數，輸出市長希望知道的已經修成的高鐵中最長的路花了多少錢。

prim算法：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_V = 510;
const int INF = 0x3f3f3f3f;
int cost[MAX_V][MAX_V];	//cost[u][v]表示邊e=(u,v)的權值(不存在的情況下設為INF) 
int mincost[MAX_V];		//從集合X出發的每個變得最小權值 
bool used[MAX_V];		//頂點i是包含在集合X中 
int V;					//頂點數 
int prim(){ 
	for(int i = 0;i < V;i ++){	//初始化 
		mincost[i] = INF;	
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;
	
	while(true){
		int v = -1;
		for(int u = 0;u < V;u ++){	//從不屬于X的頂點中選取從X到其權值最小的頂點 
			if(!used[u] && (v == -1 || mincost[u] < mincost[v]))	
				v = u;
		}
		if(v == -1)	break;
		used[v] = true;		//把頂點v加入到X 
		res = max(res, mincost[v]);//取已經生成最小生成樹中最大的 
		for(int u = 0;u < V;u ++){
			mincost[u] = min(mincost[u], cost[v][u]);
		}
	}
	return res;
}
int main(){
	int T,i,j;
	scanf("%d",&T);
	while(T --){
		scanf("%d", &V);
		for(i = 0;i < V;i ++){
			for(j = 0;j < V;j ++){
				scanf("%d",&cost[i][j]);
			}
		}
		printf("%d\n", prim());
	}
	return 0;
}
           

Kruskal算法：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_V = 510;
const int MAX_E = MAX_V*MAX_V;
const int INF = 0x3f3f3f3f;
int n, m;		//頂點數和邊數
int w[MAX_E];
int r[MAX_E];
int p[MAX_V];
int u[MAX_E],v[MAX_E];
int cmp(const int i, const int j) {
	return w[i]<w[j]; 
} //間接排序函數
int find(int x) { 
	return p[x] == x ? x : p[x] = find(p[x]);
}//并查集的find
int Kruskal() {
	int ans = 0;
	for(int i = 0; i < n; i++) 
		p[i] = i; //初始化并查集
	for(int i = 0; i < m; i++) 
		r[i] = i; //初始化邊序号
	sort(r, r+m, cmp); //給邊排序
	for(int i = 0; i < m; i++) {
		int e = r[i]; 
		int x = find(u[e]); 
		int y = find(v[e]);
		//找出目前邊兩個端點所在集合編号
		if(x != y) { ans = max(ans, w[e]); p[x] = y; } //如果在不同集合，合并
	} 
	return ans;
}
int main(){
	int T,i,j;
	scanf("%d",&T);
	while(T --){
		scanf("%d", &n);
		m = 0;
		for(i = 0;i < n;i ++){
			for(j = 0;j < n;j ++){
				u[m] = i;
				v[m] = j;
				scanf("%d",&w[m]);
				m ++;	
			}
		}
		printf("%d\n", Kruskal());
	}
	return 0;
}
           

算法模闆：prim算法  Kruskal算法