首页 > 代码库 > HDU 2122

HDU 2122

2024-07-14 03:36:31   220人阅读

题目大意很简单

就是给你城市的数量，和可以修建的铁路及其长度，如果连通，输出最小的总长，否则输出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 }
View Code

 


联系
我们