本文主要是介绍UVA10048 - Audiophobia(Floyd,最大值的最小化),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
UVA10048 - Audiophobia(Floyd,最大值的最小化)
UVA10048 - Audiophobia
题目大意:给定一无向图,每条边都有一个权值,现在给你起点和终点,要求你找出起点到终点途经的边的最大值,要求这个值尽量小,到不了输出no path。
解题思路:在floyd过程中,就可以记录下来。G【i】【j】 = min(G【i】【j】, max(G【i】【k】, G【k】【j】));
代码:
#include <cstdio>const int maxn = 105;
const int MAXD = 0x7f7f7f7f;int C, S, Q;
int G[maxn][maxn];int min (const int a, const int b) {return a < b ? a : b;
}int max(const int a, const int b) {return a > b ? a : b;
}void init () {for (int i = 1; i <= C; i++)for (int j = 1; j <= C; j++)G[i][j] = (i == j) ? 0: MAXD;
}void Floyd() {for (int k = 1; k <= C; k++)for (int i = 1; i <= C; i++)for (int j = 1; j <= C; j++) {if (G[i][k] == MAXD || G[k][j] == MAXD)continue;G[i][j] = min(G[i][j], max(G[i][k],G[k][j]));}
}int main () {int T = 0;while (scanf ("%d %d %d", &C, &S, &Q) && (C, S, Q)) {if (T)printf ("\n");init();int c1, c2, d;for (int i = 0; i < S; i++) {scanf("%d %d %d", &c1, &c2, &d);G[c1][c2] = G[c2][c1] = d;}Floyd();printf ("Case #%d\n", ++T);while (Q--) {scanf ("%d%d", &c1, &c2);if (G[c1][c2] == MAXD)printf ("no path\n");elseprintf ("%d\n", G[c1][c2]);}}return 0;
}
这篇关于UVA10048 - Audiophobia(Floyd,最大值的最小化)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!