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次。