Gorio Tech Blog search

BOJ 06086(최대 유량) 문제 풀이

12 Jul 2018 | PS Dinic Network Flow Maximum Flow

목차

참조

분류 URL
문제 최대 유량
참조 라이브러리 dinic.h, sharifa_header.h
이 글에서 설명하는 코드 06086_최대 유량

개요

시간복잡도: $ O(V^2 \cdot E) $

공간복잡도: $ O(V + E) $

문제 풀이

이 문제는 생긴 것부터가 네트워크 플로우 문제이다. Maximum Flow를 찾는 많은 알고리즘이 있지만, 디닉 알고리즘이 가장 빠르기 때문에 필자는 이 알고리즘을 사용하도록 하겠다.

구현

네트워크 플로우 문제는 모델링이 굉장히 중요한데, 이 문제는 모델링이 어렵지는 않다.

주의할 점으로는 간선을 입력받아 그래프를 생성할 때, 각 파이프가 양방향 수송이 가능하다고 하였으므로 최대 유량을 똑같이 (0이 아닌) cap으로 설정해주어야 한다는 것이다. 또 문자를 정점 번호로 변환할 때 번호가 겹치지 않도록 주의한다.

#include "../library/dinic.h"

#define MAX_V 52
#define S 0     // source
#define T 25    // sink
#define INF 1000000009

int E, cap, u, v;
Dinic network(MAX_V, S, T);

int main_06086() {
    ios::sync_with_stdio(false);    cin.tie(NULL);
    cin >> E;

    while (E--) {
        char x, y;
        cin >> x >> y >> cap;

        u = 'A' <= x && x <= 'Z' ? x - 'A' : x - 'a' + 26;
        v = 'A' <= y && y <= 'Z' ? y - 'A' : y - 'a' + 26;

        network.addEdge(u, v, cap, true);
    }

    int ans = 0;

    while (network.bfs()) {
        network.reset_next_v();
        while (true) {
            int flow = network.dfs(S, INF);
            if (!flow)
                break;
            ans += flow;
        }
    }

    cout << ans;

    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있을까?

Related Posts