首页 > 代码库 > HDU 2122
HDU 2122
题目大意很简单
就是给你城市的数量,和可以修建的铁路及其长度,如果连通,输出最小的总长,否则输出impossible
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2122
我用的prim算法一直报错也不知道为什么,后来改用Kruscal算法就好了~~T T;
正确代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include<algorithm> 5 using namespace std; 6 #define N 1010 7 #define LL long long 8 9 int n,M,S,T,C,t,k;10 LL ans;11 int fa[N];12 13 struct Path{14 int x,y,d;15 bool operator<(const Path &m)const{16 return d<m.d;17 }18 }path[10010];19 20 int getHead(int x)21 {22 int a=x;23 while(x!=fa[x]) x=fa[x];24 fa[a]=x;25 return x;26 }27 28 bool Union(int x,int y)29 {30 int fa_x=getHead(x);31 int fa_y=getHead(y);32 if(fa_x==fa_y) return false;33 fa[fa_x]=fa_y;34 return true;35 }36 37 int main()38 {39 while(scanf("%d%d",&n,&M)!=EOF){40 t=0,k=0,ans=0;41 for(int i=0;i<n;i++) fa[i]=i;42 if(n==0) {cout<<0<<endl;continue;}43 //cout<<MAXN<<endl;44 for(int i=0;i<M;i++) scanf("%d%d%d",&S,&T,&C),path[k].x=S,path[k].y=T,path[k++].d=C;45 sort(path,path+k);46 47 for(int i=0;i<k;i++){48 if(Union(path[i].x,path[i].y))49 ans+=path[i].d,t++;50 }51 52 if(t==n-1) cout<<ans<<endl;53 else cout<<"impossible"<<endl;54 cout<<endl;55 }56 return 0;57 }
错误的还未能改正好的代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 #define N 1010 6 #define MAXN 1000000000 7 #define LL long long 8 int n,M,S,T,C,count; 9 LL ans;10 int visit[N],d[N];11 int map[N][N];12 13 void prim()14 {15 int Min,MinIndex;16 memset(visit,0,sizeof(visit));17 ans=0;18 visit[0]=1,count=1;19 for(int i=1;i<n;i++) d[i]=map[0][i];20 21 for(int i=0;i<n-1;i++)22 {23 Min=MAXN,MinIndex=1;24 25 for(int i=1;i<n;i++)26 if(!visit[i]&&Min>d[i])27 Min=d[i],MinIndex=i;28 29 visit[MinIndex]=1;30 if(Min<MAXN) ans+=Min,count++;//cout<<Min<<‘ ‘;31 //cout<<ans<<endl;32 for(int i=1;i<n;i++)33 if(!visit[i]&&d[i]>map[i][MinIndex])34 d[i]=map[i][MinIndex];35 }36 }37 38 int main()39 {40 while(scanf("%d%d",&n,&M)!=EOF){41 if(n==0) {cout<<0<<endl;continue;}42 //cout<<MAXN<<endl;43 for(int i=0;i<n;i++){44 for(int j=0;j<n;j++)45 map[i][j]=MAXN;46 }47 for(int i=0;i<M;i++) scanf("%d%d%d",&S,&T,&C),map[S][T]=C,map[T][S]=C;;48 49 prim();50 51 /*for(int i=0;i<n;i++){52 for(int j=0;j<n;j++)53 cout<<map[i][j]<<‘ ‘;54 cout<<endl;55 }*/56 57 if(count==n) cout<<ans<<endl;58 else cout<<"impossible"<<endl;59 cout<<endl;60 }61 return 0;62 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。