Jungle Roads叢林道路（最小生成樹Prim&&Kruskal算法)

Jungle Roads叢林道路 POJ - 1251 

目錄

Jungle Roads叢林道路

題意描述

Kruskal算法解題思路

Kruskal AC代碼

Prim 解題思路

AC代碼

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

Input

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

Output

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.

熱帶島嶼拉格裡山的首席長老有問題。幾年前，大量外援資金被用于修建村莊之間的額外道路。但叢林無情地超越道路，是以大型道路網絡的維護成本太高。長老議會必須選擇停止維護一些道路。左上方的地圖顯示了所有正在使用的道路以及每月維護這些道路的成本（以 aacms 為機關）。當然，即使路線不像以前那麼短，也需要通過某種方式在維護的道路上到達所有村莊。首席長老想告訴長老委員會，他們每個月可以在 aacms 上花費的最少金額來維護連接配接所有村莊的道路。在上面的地圖中，村莊被标記為 A 到 I。右邊的地圖顯示了可以最便宜地維護的道路，每月 216 aacms。你的任務是編寫一個程式來解決這些問題。

輸入

輸入由1到100個資料集組成，最後一行隻包含0。 每個資料集以一行開始，隻包含一個數字n，它是村莊的數量，1 < n < 27，村莊被标記字母表的前 n 個字母大寫。每個資料集都由 n-1 行完成，這些行以字母順序以村莊标簽開頭。最後一個村莊沒有線路。一個村莊的每條線都以村莊标簽開始，然後是從這個村莊到字母表中帶有标簽的村莊的道路數量 k。如果 k 大于 0，則該行繼續包含 k 條道路中每條道路的資料。每條道路的資料是道路另一端的村莊标簽，然後是道路的每月維護成本（以 aacms 為機關）。維護成本将是小于 100 的正整數。行中的所有資料字段都由單個空格分隔。公路網将始終允許在所有村莊之間通行。該網絡的道路永遠不會超過 75 條。沒有一個村莊有超過 15 條通往其他村莊的道路（字母表中的之前或之後）。在下面的示例輸入中，第一個資料集與上面的地圖一緻。

輸出

每個資料集的每行輸出一個整數：維護連接配接所有村莊的道路系統的每月最低成本（以 aacms 為機關）。警告：檢查每組可能的道路的蠻力解決方案不會在一分鐘的時間限制内完成。

Sample Input

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0
           

Sample Output

216
30
           

題意描述：

給你多個村莊，接下來每個是與其他相連的村莊路數，以及那些村莊的編号和兩個路之間的每年維修的成本

Kruskal算法解題思路：

因為村莊的編号是abc，是以我們需要把它轉化成數字形式，我剛開始用了kruskal算法，其中會用到結構體排序和并查集來寫。

Kruskal AC代碼

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,cnt,fa[30];
struct Node
{
	int a,b,len;
}p[100];
void init()//初始化 
{
	int i;
	for(int i=1;i<=27;i++)
	{
		fa[i]=i;
	}
}
int cmp(Node x,Node y)
{
	return x.len<y.len;//結構體排序 
}
int find(int x)//并查集尋找祖先 
{
	if(x==fa[x])
		return x;
	else
		return fa[x]=find(fa[x]);//路徑壓縮 
} 
int kruskal()
{
	int rec=0;
	sort(p,p+cnt,cmp);
	double ans=0;//
	for(int i=1;i<=cnt;i++)
	{
		if(rec==n-1)
			break;//直到選用了n-1條邊之後退出循環
		int x=find(p[i].a),y=find(p[i].b);
		if(x!=y)
		{
			fa[x]=y;
			ans+=p[i].len;
			rec++;
		 } 
	}
	return ans;
}
int main(void)
{
	while(~scanf("%d",&n))
	{
		if(n==0)
		break;
		init();//初始化 
		char str[10];
		cnt=1;
		int a,b; 
		for(int i=1;i<n;i++)
		{
			scanf("%s %d",str,&a);
			int u=str[0]-'A'+1;
			for(int i=1;i<=a;i++)
			{
				scanf("%s %d",str,&b);
				int v=str[0]-'A'+1;
				p[cnt].a=u;//城市序号u 
				p[cnt].b=v;//另一個城市序号 v
				p[cnt].len=b; //它倆之間的費用 
				cnt++;
			}
		}
		printf("%d\n",kruskal());
	}
	return 0;
}
           

Prim 解題思路：

和kruskal差不多，把字元轉換成數字形式，然後把村莊的距離存入二維數組裡面，利用prim求最短路并相加，最後輸出即可，注意字元串和二維數組初始化

AC代碼

#include<stdio.h>
#include<string.h>
#define N 100
int inf=999999;
int e[N][N],book[N],dis[N];
int main(void)
{
	int n,ans,min,u,v,a,b;
	while(~scanf("%d",&n))
	{
		char s[N];
		memset(dis,0,sizeof(dis));
		memset(s,0,sizeof(s));
		ans=0;
		if(n==0)
		break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i==j) e[i][j]=0;
				else e[i][j]=inf;
		for(int i=1;i<n;i++)
		{
			scanf("%s %d",s,&a);
			int x=s[0]-'A'+1;
			for(int j=1;j<=a;j++)
			{
				scanf("%s %d",s,&b);
				int y=s[0]-'A'+1;
				e[x][y]=e[y][x]=b;
			}
		}
		for(int i=1;i<=n;i++)
		{
			dis[i]=e[1][i];
			book[i]=0;
		}
		book[1]=1;
		for(int i=1;i<n;i++)
		{
			int min=inf;
			for(int j=1;j<=n;j++)
			{
				if(dis[j]<min&&book[j]==0)
				{
					min=dis[j];
					u=j;
				}
			}
			book[u]=1;
			ans+=dis[u];
			for(v=1;v<=n;v++)
			{
				if(book[v]==0&&dis[v]>e[u][v])
				dis[v]=e[u][v];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}