uva 10099 The Tourist Guide

city 的數量最多會到 100，worst case : complete graph : 有 100 * 99 roads，所以至少要

100 * 99 大小的 maps。

因為一次的載客量是依據這條路徑的最小 weight，所以這條路徑上的 weight 盡量越大越好，

形成 spanning tree，但是是從最大 weight 的 edge 開始選起，直到起點和終點有連通，即可

停止，走目前的路徑即可得到最少的載客次數，如果再往下挑，會挑到越小的 weight，不會

有更好的解。


#include <stdio.h>
#include <stdlib.h>

struct road{
    int start;
    int dest;
    int tourist;
};
struct road maps[120*120];

int city_set[120]={0};

int compare(const void *a, const void *b){
    return  ((struct road *)b)->tourist - ((struct road *)a)->tourist;
}

int find_p(int num){
    while(city_set[num]>0)
        num=city_set[num];

    return num;
}

int main(void){
    int city, road;
    int start, dest,tourist;
    int scenario=0,i;
    int p1,p2;

    while(scanf("%d %d",&city,&road)!=EOF){
        ++scenario;
        if(city==0&&road==0){
            break;
        }

        for(i=0;i<road;i++){
            scanf("%d %d %d",&maps[i].start, &maps[i].dest, &maps[i].tourist);
        }

        for(i=1;i<=city;i++){
            city_set[i]=-1;
        }

        scanf("%d %d %d",&start,&dest,&tourist);

        qsort(maps,road,sizeof(struct road),compare);

        for(i=0;i<road;i++){
            p1=find_p(maps[i].start); p2=find_p(maps[i].dest);

            if(p1!=p2){
                city_set[p1]=p2;
                if( find_p(start) == find_p(dest) )
                    break;
            }
        }

        printf("Scenario #%d\n",scenario);
        printf("Minimum Number of Trips = ");
        if(start==dest){
            printf("1\n\n");
        }else{
            --maps[i].tourist;
            if(tourist%maps[i].tourist !=0){
                printf("%d\n\n", (tourist/maps[i].tourist)+1 );
            }else{
                printf("%d\n\n", (tourist/maps[i].tourist) );
            }
        }

    }

    return 0;
}