本文主要是介绍hdu1232另类解法Prim，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
Sample Output
1
0
2
998
最近有几个朋友问我这个题目，然后我就讲了我用Prim算法AC了，然而网上的大多参考代码都是用并查集做的。所以，作为一个补充，我想说说我自己的解法。（AC不需要标准答案，可能我这解法还没并查集高效，但分享出来吧。）然而作为一个刚玩几天的ACMer，还没学并查集，我当时看到这题目的时候。我觉得应该是用最小生成树做，不会并查集，所以首选Prim。
先上代码，你们先体会体会。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;//正无穷
const int MAXN=1010;
bool vis[MAXN];//记录该点是否被访问
int lowc[MAXN];//lowc[i]表示从当前树到i点的最小权值
int cost[MAXN][MAXN];//最初两点之间的权值
int flag;
int Prim(int n,int start)//点是0~n-1
{int ans=1;if(0==flag)//vis只在第一次调用Prim的时候初始化。{memset(vis,false,sizeof(vis));flag=1;}for(int i=1;i<n;i++)lowc[i]=cost[start][i];vis[start]=true;for(int i=1;i<n;i++){int minc=INF;int p=-1;for(int j=0;j<n;j++)if(!vis[j]&&minc>lowc[j]){minc=lowc[j];p=j;}if(minc==INF)//这里本来是判断图不连通的条件{for(int j=1;j<n;j++){if(!vis[j])ans+=Prim(n,j);}return ans;}vis[p]=true;for(int j=0;j<n;j++)if(!vis[j]&&lowc[j]>cost[p][j])lowc[j]=cost[p][j];}return ans;
}
int main()
{int n,m,a,b,i,j,ans;while(1){scanf("%d",&n);if(n==0)break;memset(cost,INF,sizeof(int)*MAXN*MAXN);scanf("%d",&m);if(m==0){cout<<n-1<<endl;continue;}for(i=0;i<m;i++){scanf("%d%d",&a,&b);cost[a-1][b-1]=1;cost[b-1][a-1]=1;}flag=0;ans=Prim(n,0)-1;cout<<ans<<endl;}
}我这里用的点是[0, n-1]，注意。
大体还是常规的Prim算法，Prim本来的返回值应该是最小生成树的权值，或者返回这不是一个连通图。我这里把它改了。Prim返回不是连通图时，已经是把所有能访问的点访问过了。所以在这里，我们选一个无法访问的点，继续Prim，然后递归进去。直到所有点都访问过了，然后一层一层返回。返回的值就是递归调用了几次Prim，所以就是把原来的图，用最小生成树的方式，变成了森林，所以只要树的棵树减1，就是最少还需要建的路的数量。
这篇关于hdu1232另类解法Prim的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
