BAEKJOON 2679 - Route Redundancy

문제: https://www.acmicpc.net/problem/2679

문제

A city is made up exclusively of one-way streets. Each street in the city has a capacity, the maximum number of cars it can carry per hour. Any route (path) also has a capacity, which is the minimum of the capacities of the streets along that route.

The redundancy ratio from point A to point B is the ratio of the maximum number of cars that can get from A to B in an hour using all routes simultaneously, to the maximum number of cars that can get from A to B in an hour using just one route. The minimum redundancy ratio is the number of cars that can get from A to B in an hour using all possible routes simultaneously, divided by the capacity of the single route with the largest capacity.

입력

The first line of input contains a single integer P, ( 1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set consists of several lines and represents a directed graph with positive integer weights.

The first line of each data set contains five space separated integers. The first integer, D is the data set number. The second integer, N ( 2 ≤ N ≤ 1000), is the number of nodes in the graph. The third integer, E, (E > 1), is the number of edges in the graph. The fourth integer, A, ( 0 ≤ A < N), is the index of point A. The fifth integer, B, ( 0 ≤ B < N, A ≠ B), is the index of point B.

The remaining E lines describe each edge. Each line contains three space separated integers. The first integer, U ( 0 ≤ U < N), is the index of node U. The second integer, V ( 0 ≤ V < N, V ≠ U), is the index of node V. The third integer, W ( 1 ≤ W < 1000), is the capacity (weight) of the path from U to V.

출력

For each data set there is one line of output. It contains the data set number (N) followed by a single space, followed by a floating-point value which is the minimum redundancy ratio to 3 digits after the decimal point.

예제 입력 

1
7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

예제 출력 

1.667

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2011 Greater New York Programming Contest E번

• 문제를 번역한 사람: baekjoon

링크

• ACM-ICPC Live Archive
• HDU Online Judge

알고리즘 분류

• 네트워크 플로우

모든 길을 이용한 최대 유량은 알고리즘 책에서 공부했던 network flow (Ford Fulkerson algorithm) 방법으로 얻을 수 있었고,

한 개의 도로만을 이용한 최대 유량은 깊이 우선 탐색으로 얻을 수 있었습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <vector>
#include <queue>
#include <iomanip> 
using namespace std;
 
const int MAX_N = 1000;
int capacity[MAX_N][MAX_N];
int flow[MAX_N][MAX_N];
int N, source, sink;
 
int getMaxFlow_dfs(int here, int minFlow, vector<bool>& visited)
{
    if (here == sink)
        return minFlow;
 
    int ret = 0;
    for (int next = 0; next < N; next++)
    {
        if (visited[next])
            continue;
        if (next == here)
            continue;
        if (capacity[here][next] == 0 || capacity[here][next] < ret)
            continue;
        visited[next] = true;
        ret = max(ret, getMaxFlow_dfs(next, min(minFlow, capacity[here][next]), visited));
        visited[next] = false;
    }
    return ret;
}
 
int getTotalFlow_networkFlow_bfs()
{
    memset(flow, 0, sizeof(flow));
    int totalFlow = 0;
 
    while (true)
    {
        vector<int> parent(N, -1);
        queue<int> q;
        parent[source] = source;
        q.push(source);
        while (!q.empty())
        {
            int here = q.front();
            q.pop();
            for (int next = 0; next < N; next++)
            {
                if (capacity[here][next] - flow[here][next] > 0 && parent[next] == -1)
                {
                    q.push(next);
                    parent[next] = here;
                }
            }
        }
 
        if (parent[sink] == -1)
            break;
 
        int amount = INT_MAX;
        for (int p = sink; p != source; p = parent[p])
            amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
 
        for (int p = sink; p != source; p = parent[p])
        {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        totalFlow += amount;
    }
 
    return totalFlow;
}
 
int main()
{
    int T;
    cin >> T;
    for (int t = 0; t < T; t++)
    {
        int E;
        cin >> N >> E >> source >> sink;
 
        memset(capacity, 0, sizeof(capacity));
 
        for (int i = 0; i < E; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            capacity[a][b] = c;
        }
 
        int totalFlow = getTotalFlow_networkFlow_bfs();
 
        vector<bool> visited(N, false);
        int maxFlow = getMaxFlow_dfs(source, INT_MAX, visited);
        cout << fixed << setprecision(3) << (double)totalFlow / (double)maxFlow << endl;
    }
    return 0;
}