程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA10048 - Audiophobia(Floyd,最大值的最小化)

UVA10048 - Audiophobia(Floyd,最大值的最小化)

編輯:C++入門知識

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 

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");
            else
                printf ("%d\n", G[c1][c2]);
        }
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved