henrytb 的博客

henrytb 的博客

题解 UVA10048 【噪音恐惧症 Audiophobia】

posted on 2019-02-17 11:57:29 | under 题解 |

这是一个Floyd的扩展

就是求图上任意两点之间的使最大边权最小的路径啦QAQ

所以,我们可以稍微对Floyd进行一些微小的改动:

f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

改成

f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));

就AC了QAQ

我们这里 $f[i][j]$ 的意思是 $i$ 到 $j$ 的路径中,使噪声最大的路径最小的方案里的噪声最大的路径的权值

正确性证明:类似Floyd,略

附代码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,m,q,now,f[105][105];
int main(){
    while(~scanf("%d%d%d",&n,&m,&q)&&n){
        memset(f,0x3f3f3f3f,sizeof(f));
        rep(i,1,m){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            f[u][v]=w;
            f[v][u]=w;
        }
        rep(k,1,n)rep(i,1,n)rep(j,1,n){
            f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));
        }
        if(now)printf("\n");
        printf("Case #%d\n",++now);
        rep(i,1,q){
            int a,b;
            scanf("%d%d",&a,&b);
            if(f[a][b]==0x3f3f3f3f)printf("no path\n");
            else printf("%d\n",f[a][b]);
        }
    }
    return 0;
}