uva 10048 - Audiophobia

点击打开链接uva 10048

题目意思：

现在城市污染很严重，除了平常的污染外还有什么声音污染。现在有c个城市，s个街道，每一个街道有一个声音的分贝值。现在由于从某一点到另外一点有很多条路径，现在要求我们找到一条路径中使得这条路径上的最大的声音分贝是所有可达路径中最小的。如果没有输出“no path”，否则额输出这个最小值。

思路：最小生成树+kruskal

要求：所有满足能够到达终点的路径中一条边的最大值中的最小值，那么自然跟最小生成树联系起来

分析：利用kruskal的算法的思想，我们先把所有的要求的路径保存起来。那么利用kruskal开始生成树，每加入一个连通分量的我们就去判断所有要求的路径中是否已经在同一个连通分量里面并且没有求过，因为我们知道如果两个点在这一次合并后变成同一个连通分量，那么这两个点的最短路已经形成，并且由于kruskal的性质上一次加入的边长度肯定比下一次加入的小。所以可以知道这个路径要求的ans 就是当前的这个边的权值（具体好好想想，表达能力实在有限）。

代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110

int c , s , q , cnt;
int father[MAXN];
int rank[MAXN];
int ans[10010];
struct query{
    int x;
    int y;
}que[10010];
struct Edge{
    int x;
    int y;
    int value;
}e[1010];

bool cmp(Edge e1 , Edge e2){
     return e1.value < e2.value;
}

void init_Set(){
     for(int i = 1 ; i <= c ; i++){
        father[i] = i;
        rank[i] = 1;
     }
}

int find_Set(int x){
    int tmp = x;
    while(father[tmp] != tmp)
       tmp = father[tmp];
    while(father[x] != tmp){
       int tmp_x = father[x];
       father[x] = tmp;
       x = tmp_x;
    }
    return tmp;
}

void union_Set(int x, int y){
     if(rank[x] >= rank[y]){
        rank[x] += rank[y];
        father[y] = x;
     }
     else{
        rank[y] += rank[x];
        father[x] = y;
     }
}

void judge(int x){
     for(int i = 0 ; i < q ; i++){
        if(find_Set(que[i].x) == find_Set(que[i].y) && !ans[i])
          ans[i] = e[x].value;
     }
}

void Kruskal(){
     printf("Case #%d\n" , cnt++);     
     init_Set();
     sort(e , e+s , cmp);
     memset(ans , 0 , sizeof(ans));
     for(int i = 0 ; i < s ; i++){
         int root_x = find_Set(e[i].x);
         int root_y = find_Set(e[i].y); 
         if(root_x != root_y){
            union_Set(root_x , root_y);
            judge(i);
         }
     }
     for(int i = 0 ; i < q ; i++){
        if(ans[i])
          printf("%d\n" , ans[i]);
        else
          printf("no path\n");
     }
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    int flag = 1;
    cnt = 1;
    while(scanf("%d%d%d" , &c , &s , &q) && c+s+q){
        for(int i = 0 ; i < s ; i++)
           scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value);
        for(int i = 0 ; i < q ; i++)
           scanf("%d%d" , &que[i].x , &que[i].y);
        if(flag)
          flag = 0;
        else
          printf("\n");
        Kruskal();
    }
    return 0;
}