PTA:7-121 暢通工程之局部最小花費問題 (35分)(Prim-普裡姆算法+解析)

7-121 暢通工程之局部最小花費問題 (35分)

某地區經過對城鎮交通狀況的調查，得到現有城鎮間快速道路的統計資料，并提出“暢通工程”的目标：使整個地區任何兩個城鎮間都可以實作快速交通（但不一定有直接的快速道路相連，隻要互相間接通過快速路可達即可）。現得到城鎮道路統計表，表中列出了任意兩城鎮間修建快速路的費用，以及該道路是否已經修通的狀态。現請你編寫程式，計算出全地區暢通需要的最低成本。

輸入格式:

輸入的第一行給出村莊數目N (1≤N≤100)；随後的N(N−1)/2行對應村莊間道路的成本及修建狀态：每行給出4個正整數，分别是兩個村莊的編号（從1編号到N），此兩村莊間道路的成本，以及修建狀态 — 1表示已建，0表示未建。

輸出格式:

輸出全省暢通需要的最低成本。

輸入樣例:

4

1 2 1 1

1 3 4 0

1 4 1 1

2 3 3 0

2 4 2 1

3 4 5 0

輸出樣例:

3

思路

題目大意就是建構最小生成樹。這裡使用的普裡姆算法。

如果對讀者對普裡姆算法不懂的話，推薦看部落格：https://blog.csdn.net/yeruby/article/details/38615045，部落客寫的很詳細，很清晰。

下面的是我個人的一些了解：

算法思想：設圖G頂點集合為U，首先任意選擇圖G中的一點作為起始點a，将該點加入集合V，再從集合U-V中找到另一點b使得點b到V中任意一點的權值最小，此時将b點也加入集合V；以此類推，現在的集合V={a，b}，再從集合U-V中找到另一點c使得點c到V中任意一點的權值最小，此時将c點加入集合V，直至所有頂點全部被加入V，此時就建構出了一顆MST。因為有N個頂點，是以該MST就有N-1條邊，每一次向集合V中加入一個點，就意味着找到一條MST的邊。

個人了解： 也就是找一點A作為開始點，然後找到另一個距離開始點最近的點B連接配接起來，接着再找一個點C（點C是離點A或者點B最近的那一點），接下來的D點也就是到A,B,C點中最近的那一點，依此類推連接配接所有點，構成最小生成樹。

具體代碼解釋見AC代碼：

#include<bits/stdc++.h>
using namespace std;
int dist[101],cost[101][101],vis[101];
int n,m,i,j,sum=0;

int main(){
	cin>>n; 
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			cost[i][j]=cost[j][i]=1e9;	
		}
	}
	m=n*(n-1)/2;
	int x,y,dis,z;
	while(m--){
		cin>>x>>y>>dis>>z;
		if(z==0) cost[x][y]=cost[y][x]=dis;
	}
	for(i=1;i<=n;i++) dist[i]=cost[1][i];  //dist[i]表示1為起點i為終點的邊的權值 
	vis[1]=1;
	dist[1]=0;
	for(i=1;i<n;i++){
		int min=1e9,k=-1;
		for(j=1;j<=n;j++){
			if(!vis[j]&&dist[j]<min){   //找到未通路 而且 距離已通路結點最短的結點 
				min=dist[j];
				k=j;
			}
		}
		vis[k]=1;  //找到最優的結點，構成一條新的最優邊 
		if(k!=-1){  
			sum=sum+dist[k];//總權值 
			for(j=1;j<=n;j++){
				if(!vis[j]&&dist[j]>cost[k][j]){  //更新權值 
					dist[j]=cost[k][j];
				} 
			}
		}
	}
	cout<<sum<<endl; 
	return 0;
}
           

我這兩個算法總是搞混，下面是差別

Prim (普裡姆)算法和Dijkstra (迪傑斯特拉)的差別

(1)分析對象不同,前者為無向圖,後者為有向圖。

(2)連通的頂點不同，前者連通所有頂點，且總的代價最低，後者為單源點多目标點最短路徑，所求得的是兩頂點之間代價最小。

(3)普裡姆算法生成最小生成樹需重複n-1次，迪傑斯特拉算法則需重複n-2次。