#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;
    
}

• RP问题上错了 (1753) Qinz 2008-11-11 18:14:13
  • Re:膜拜大牛，告诉我哪错了，我就归你了 (0) Faker 2008-11-11 18:14:39