1 // TOJ 2119 最小生成树  2   3 #include <iostream>  4 #include <cstdio>  5 #include <cstring>  6 #include <map>  7 using namespace std;  8   9 const int size = 520; 10 const double inf = 888888888.0; 11 double length; 12 int n; 13 string name; 14 struct data 15 { 16     int num; 17     int next[50]; 18     double dist[50]; 19 }edge[size]; 20 map<string,int>mp; 21 bool vis[size]; 22 double dist[size]; 23  24 void prim() 25 { 26     int i , j , k; 27     memset( vis , false , sizeof(false) ); 28     for( i = 0 ; i<size ; i++ ) 29     { 30         dist[i] = (i==0)?0:inf; 31     } 32     for( i = 0 ; i<edge[0].num ; i++ ) 33     { 34         dist[ edge[0].next[i] ] = edge[0].dist[i]; 35     } 36     vis[0] = true; 37     double ans = 0; 38     double mmin; 39     for( i = 1 ; i<n ; i++ ) 40     { 41         mmin = inf; 42         for( j = 1 ; j<n ; j++ ) 43         { 44             if( !vis[j] && dist[j]<mmin ) 45             { 46                 mmin = dist[j]; 47                 k = j; 48             } 49         } 50         if( mmin == inf ) 51         { 52             break; 53         } 54         vis[k] = true; 55         ans+=mmin; 56         for( j = 0 ; j<edge[k].num ; j++ ) 57         { 58             if( dist[ edge[k].next[j] ] > edge[k].dist[j]  && !vis[ edge[k].next[j] ]  ) 59             { 60                 dist[ edge[k].next[j] ] = edge[k].dist[j]; 61             } 62         } 63     } 64     if( ans<=length ) 65         printf( "Need %.1lf miles of cable\n",ans ); 66     else 67         printf( "Not enough cable\n" ); 68 } 69  70 int main() 71 { 72     char st[30] , end[30]; 73     double len;         74     int m; 75     int cnt; 76     while( ~scanf("%lf",&length) ) 77     { 78         mp.clear(); 79         for( int i = 0 ; i<size ; i++ ) 80             edge[i].num = 0; 81         cnt = 0; 82         scanf( "%d",&n ); 83         for ( int i = 0 ; i<n ; i++ ) 84         { 85             cin>>name; 86             mp[name] = cnt++;  // 将人名映射为数字 87         } 88         scanf( "%d",&m ); 89         while( m-- ) 90         { 91             scanf( "%s %s %lf",st,end,&len ); 92             int x = mp[st]; 93             int y = mp[end]; 94             edge[x].next[ edge[x].num ] = y; 95             edge[x].dist[ edge[x].num++ ] = len; 96             edge[y].next[ edge[y].num ] = x; 97             edge[y].dist[ edge[y].num++ ] = len; 98         } 99         prim();100     }101     return 0;102 }