首页 > 代码库 > Prim算法POJ1258
Prim算法POJ1258
http://poj.org/problem?id=1258
这道题是最简单的一个啦,,,,
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 const int N=110; 7 #define M 0x3f3f3f3f///设置无穷大的数M,当两点之间无法联通时设两者之间距离为M 8 int ma[N][N],low[N],vis[N];///ma记录道路的长度,low记录最短的路径,vis判断是否经过这点 9 int n;10 int prim(){11 int i,j,pos,mi,result=0;12 memset(vis,0,sizeof(vis));13 vis[1]=1;///从1开始遍历14 pos=1;///记录当前结点15 16 17 for(i=1;i<=n;i++)18 if(i!=pos)low[i]=ma[pos][i];///,初始时pos等于1,查找pos周围可以通过的结点中最短的距离并存储在low中19 20 21 for(i=1;i<n;i++){///遍历n-1次22 mi=M;23 for(j=1;j<=n;j++){24 if(vis[j]==0&&mi>low[j]){25 mi=low[j];26 pos=j;27 28 }29 }30 result+=mi;31 vis[pos]=1;32 for(j=1;j<=n;j++){///查找pos周围的最短的距离33 if(vis[j]==0&&low[j]>ma[pos][j])34 low[j]=ma[pos][j];35 }36 }37 return result;38 }39 int main()40 {41 int i,v,j,ans;42 while(~scanf("%d",&n)){43 memset(ma,M,sizeof(ma));44 for(i=1;i<=n;i++){45 for(j=1;j<=n;j++){46 scanf("%d",&v);47 ma[i][j]=ma[j][i]=v;48 49 }50 }51 ans=prim();52 cout<<ans<<endl;53 }54 return 0;55 }
Prim算法POJ1258
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。