> #include<iostream>
> #include<cstring>
> using namespace std;
> double map[1001][1001];
> double cost[1001];
> int close[1001];
> char name[1001][21];
> int n,m;
> double sum,len,tol;
> char s1[21],s2[21];
> void prim(int v)
> {   int i,j,k;
>     for(i=1;i<=n;i++)
>     {   cost[i]=map[v][i];
>         close[i]=v;
>     }
>     for(i=1;i<n;i++)
>     {    double minn=1000000000;
>          for(j=1;j<=n;j++)
>          {   
>              if(cost[j]>0&&minn>cost[j])
>              {   
>                  minn=cost[j];
>                  k=j;
>                  
>              }
>          }
>          sum+=minn;
>          cost[k]=0;
>          for(j=1;j<=n;j++)
>          {   
>              if(cost[j]>0&&map[k][j]>0&&map[k][j]<cost[j])
>              {    cost[j]=map[k][j];
>                   close[j]=k;
>              }
>          }
>     }
> }
> int check(char *s)
> {   int i;
>     for(i=1;i<=n;i++)
>        if(strcmp(name[i],s)==0)
>           return i;
> }
> int main()
> {   sum=0.0;
>     memset(map,0,sizeof(map));
>     memset(close,0,sizeof(close));
>     memset(cost,0,sizeof(cost));
>     int i,j,k;
>     scanf("%lf",&tol);
>     scanf("%d",&n);
>     getchar();
>     for(i=1;i<=n;i++)
>     {   scanf("%s",name[i]);
>     }
>     scanf("%d",&m);
>     getchar();
>     int a,b;
>     for(i=1;i<=m;i++)
>     {   scanf("%s %s %lf",s1,s2,&len);
>         getchar();
>         a=check(s1);
>         b=check(s2);
>         map[a][b]=len;
>         map[b][a]=len;
>     }
>     prim(1);
>     if(sum>tol)
>        printf("Not enough cable\n");
>     else printf("Need %.1lf miles of cable\n",sum);
>     system("pause");
>     return 0;
>     
> }

• Re:膜拜大牛，告诉我哪错了，我就归你了 (0) Faker 2008-11-11 18:14:39