首页 > 代码库 > XXy
XXy
XXy
codevs1003
帮我看看
#include<iostream>#include<cstdio>using namespace std;int dis[200],map[200][200],n,num,cost,fa[200],point[200];bool vis[200];void Prim(int s,int t){ for(int i=1;i<=n;i++)dis[i]=0x7f; dis[s]=0;int pre=1; for(int i=1;i<=n;i++){ int Min=0x7f,k=0; for(int j=1;j<=n;j++){ if((dis[j]<Min)&&(vis[j]==0)) Min=dis[j],k=j,point[num]=k; } if(Min==0x7f)break; cost+=Min; vis[k]=1; for(int j=1;j<=n;j++){ if((map[k][j]<dis[j])&&(vis[j]==0))dis[j]=map[k][j],fa[j]=k; } if(Min!=0)num++; pre=k; }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>map[i][j]; Prim(1,n); cout<<num<<endl; for(int i=0;i<num;i++) if(fa[point[i]]<point[i])cout<<fa[point[i]]<<‘ ‘<<point[i]<<endl; else cout<<point[i]<<‘ ‘<<fa[point[i]]<<endl; cout<<cost;}
XXy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。