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 }

View Code