[백준] 2679번 - 맨체스터의 도로

문제

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

Network Flow + DFS

 

'A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.'

 

A. A에서 B로 가는 모든 길을 동시에 이용하는 경우

B. 길 1개를 이용했을 때 도착할 수 있는 경우

A / B를 구하시오.

 

원문이 번역된 문제라, 뭔 소리인가 몇 번 읽어봤다.

 A는 최대유량을 구하라는 의미이고, B는 최대유량으로 구해지는 source->sink의 경로 중 하나에 대한 최대유량을 의미한다.

 

B의 경우에는 최대유량, 다익스트라 돌려보다 결국 DFS로 다 돌렸다.

해당 길을 이루는 간선들 중 최소 용량을 가지고 가면서 DFS를 돌려주면 된다.

 

초기화 까먹고 이왜않하다가 계속 틀린듯

 

코드

#include<iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
int T;
//정점개수, 간선 수, A->B
int N, E, A, B;
int capacity[1001][1001];
int flow[1001][1001];
struct Node {
    int n, c;
    bool operator<(Node o) const {
        return c < o.c;
    }
};
vector<Node> graph[1001];
int networkFlow(int source, int sink)
{
    int result = 0;
    while (true)
    {
        int parent[1001];
        memset(parent, -1, sizeof(parent));
        queue<int> q;
        q.push(source);
        parent[source] = source;

        while (!q.empty() && parent[sink] == -1) {
            int now = q.front();
            q.pop();
            for (int i = 0; i < N; ++i) {
                if (capacity[now][i] - flow[now][i] <= 0) continue;
                if (parent[i] == -1) {
                    parent[i] = now;
                    q.push(i);
                }
            }
        }

        if (parent[sink] == -1) break;

        int mv = 1987654321;
        for (int i = sink; i != source; i = parent[i]) {
            mv = min(mv, capacity[parent[i]][i] - flow[parent[i]][i]);
        }

        for (int i = sink; i != source; i = parent[i]) {
            flow[parent[i]][i] += mv;
            flow[i][parent[i]] -= mv;
        }
        result += mv;
    }
    return result;
}
int visited[1001];
int answer = 0;
void dfs(int nxt, int v) {
    if (nxt == B) {
        answer = max(v, answer);
        return;
    }
    for (int i = 0; i < graph[nxt].size(); ++i) {
        if (visited[graph[nxt][i].n]) continue;
        visited[graph[nxt][i].n] = 1;
        dfs(graph[nxt][i].n, min(v, graph[nxt][i].c));
        visited[graph[nxt][i].n] = 0;
    }
}
void solve() {
    for (int i = 0; i < N; ++i) graph[i].clear();
    answer = 0;
    memset(visited, 0, sizeof(visited));
    memset(capacity, 0, sizeof(capacity));
    memset(flow, 0, sizeof(flow));

    cin >> N >> E >> A >> B;
    for (int i = 0; i < E; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        capacity[a][b] = c;
        graph[a].push_back({ b, c });
    }
    visited[A] = 1;
    dfs(A, 1987654321);
    cout << (float(networkFlow(A, B)) / answer) << " ";
}
int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(3);
    cout << fixed;
    cin >> T;
    for (int i = 0; i < T; ++i) {
        solve();
    }
    return 0;
}