畅通工程 HDU1863——普里姆算法

本文主要是介绍畅通工程 HDU1863——普里姆算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

Sample Output

3
?

很明显，最小生成树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>const int INF=99999999;int m,n;
int map1[110][110];
int dis[110];
int vis[110];void prim()
{int i,k,min1,j,js=0,flag=0;memset(vis,0,sizeof(vis));//清理标记数组为0for(i=1;i<=m;i++){dis[i]=map1[1][i];//初始化}vis[1]=1;//第一个点作为起始点，表示已访问for(i=1;i<=m-1;i++){min1=INF;k=0;for(j=1;j<=m;j++){if(vis[j]==0&&min1>dis[j]){min1=dis[j];k=j;}}//通过这个for循环来找当前dis数组中最短的一条路js+=min1;//找到后加入到权值中vis[k]=1;//表示这个最小的点已经被访问for(j=1;j<=m;j++){if(vis[j]==0&&dis[j]>map1[k][j]){dis[j]=map1[k][j];//这个很像地杰斯特拉里面的松弛算法//但这里是把未被访问过的和已经加入树里的最短的点放到//dis数组中}}}for(i=1;i<=m;i++){if(vis[i]==0){flag=1;//如果发现标记数组中有未被加入点，就说明有某个点//或某些点不可达到break;}}if(flag==1){printf("?\n");}else{printf("%d\n",js);}
}int main()
{int i,x,y,z,j;while(scanf("%d%d",&n,&m),n){for(i=0;i<=m;i++){for(j=0;j<=m;j++){map1[i][j]=INF;//初始化if(i==j){map1[i][j]=0;}}}for(i=0;i<n;i++){scanf("%d%d%d",&x,&y,&z);if(map1[x][y]>z){map1[x][y]=z;map1[y][x]=z;}}prim();}return 0;
}

这篇关于畅通工程 HDU1863——普里姆算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！