TIOJ 1162 5.小氣又愛現的老薑

poao899    72K    31MS    G++    1.32K     2009-11-12 23:36:19                                        .


唔囧純粹MST

本來想要鍊map不過看起來挑錯題了囧


//********************************

//1162 MST + map

#include<stdio.h>
#include<algorithm>
char city[60][40];
struct road{
    char name[40];
    int i,j,len,order;
    bool use;
    void set(int o){
        order=o;
        scanf("%s%d%d%d",name,&i,&j,&len);
        use=0;
    }
    bool operator<(const road &b)const{
        return len==b.len?order<b.order:len<b.len;
    }
}E[3000];
bool cmp(road a,road b){
    return a.order<b.order;
}
int n,root[60],m,edgeAdded,total;
int find(int a){
    return a==root[a]?a:root[a]=find(root[a]);
}
main(){
    while(scanf("%d",&n),n){
        //Initialize
        for(int i=0;i<60;i++){
            root[i]=i;
        }
        edgeAdded=0;total=0;
        //Input CityName
        for(int i=0;i<n;i++)
            scanf("%s",city[i]);
        //Input Edge
        scanf("%d",&m);
        for(int i=0;i<m;i++)
            E[i].set(i);
        scanf("%*s");
        //MST
        std::sort(E,E+m);
        for(int i=0;i<m&&edgeAdded<n-1;i++){
            int ra=find(E[i].i),rb=find(E[i].j);
            if(ra!=rb){
                E[i].use=1;
                edgeAdded++;
                root[ra]=rb;
                total+=E[i].len;
            }
        }
        //Output
        int cnt=1;
        std::sort(E,E+m,cmp);
        for(int i=0;i<m;i++)
            if(E[i].use)
                printf("#%d Road is named %s, connect %s and %s,length=%d\n",cnt++,E[i].name,city[E[i].i<?E[i].j],city[E[i].i>?E[i].j],E[i].len);

        printf("Jiang will spend %d TMTdollars.\n",total*100);
    }
}