PTA:7-121 畅通工程之局部最小花费问题 (35分)(Prim-普里姆算法+解析)

  • Post author:
  • Post category:其他




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



版权声明:本文为weixin_43581819原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。