UVa 11874 - Travel Company

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

給一個 N 個城市的地圖，每一條路徑上會有成本和獲益，希望找到一條送貨的環道，是否存在一個環道使得獲益是成本的 P 倍。

Sample Input

3
5 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 1
3 0 11 6

5 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 2
3 0 11 6

5 8 2
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 5
3 0 11 6

Sample Output

Case 1: YES
Case 2: NO
Case 3: YES

Solution

最小比例環的應用，事實上可以把題目化簡為負環檢查，將每一條邊的權重定義為 expense * p - income，只要負環存在則存有一條環道的 獲益/成本 > P

點數很少，直接用 floyd 在 O(n^3) 找解。

#include <stdio.h> 
#include <string.h>
#include <algorithm> 
using namespace std;

int g[128][128];
int main() {
    int testcase, cases = 0;
    int n, m, p, x, y, income, expense;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &n, &m, &p);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                g[i][j] = 0xf3f3f3f;
        while(m--) {
            scanf("%d %d %d %d", &x, &y, &income, &expense);
            g[x][y] = min(g[x][y], expense * p - income);
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
        int ret = 0;
        for(int i = 0; i < n; i++)
            ret |= g[i][i] < 0;
        printf("Case %d: %s\n", ++cases, ret ? "YES" : "NO");
    }
    return 0;
}