本文主要是介绍UVA 10048 - Audiophobia（flody算法应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
到了图论这一章果然感觉自己很吃力。
flody 本身是求任意两点间的最短路。 应用的是 dp的思想。 d【i】【j】 = min（d【i】【j】，d【i】【k】 + d【k】【j】）；
for(int k = 0; k < n; k++){
for(int j = 0; j < n; j++）{
for（int k = 0; k < n; k++){
if(d[i][j] < INF && d[k][j] < INF)
d[i][j] = min(d[i][j] , d[i][k] + d[k][j]);
}
}
}
i 到j的最短距离 必然是 中间某一点k i到k的最短距离 + k到j的最短距离之和。
这个题是 求 一点 到另一点的 最大噪音最小值。 那么我们要求出 i 到 j的 所有的 路 中 噪音的最小的那个。
自然 就 改成 d【i】【j】 = min（d【i】【j】，max（d【i】【k】 ，d【k】【j】））
因为 从i到 j 这条路中 最大的噪音 一定 是 d【i】【k】 和 d【k】【j】 中最大的噪音。 （此时的 d 数组 代表的时候 i 到 j 最大的噪音）
理解之后 就很简单了
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define ll long long
typedef unsigned long long ull;
#define maxn 1000+10
#define INF 10000000
int d[maxn][maxn];
int main (){int n,str,num;int counts = 0;while(scanf("%d%d%d",&n,&str,&num) && n && str && num){if(counts)printf("\n");for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j) d[i][j] = 0;else d[i][j] = INF;}}for(int i = 0; i < str; i++){int a,b,v;scanf("%d%d%d",&a,&b,&v);d[a][b] = v;d[b][a] = v;}for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));}}}printf("Case #%d\n",++counts);while(num--){int a,b;scanf("%d%d",&a,&b);if(a == b || d[a][b] >= INF)printf("no path\n");elseprintf("%d\n",d[a][b]);}}return 0;
}
这篇关于UVA 10048 - Audiophobia（flody算法应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
