[BOJ] 6086번: 최대 유량

6086번: 최대 유량

제한 조건
- 시간 제한 : 1s
- 공간 제한 : 128MB

풀이 사용 
- 사용 언어 : C++17
- 사용 시간 : 0ms
- 사용 공간 : 1352KB
- 시도 회수 : 6회

풀이 설명
- 최대 유량문제
- Ford-Fulkerson method에서 augmenting path를 DFS순서대로 찾는 Edmonds-Karp Algorithm을 사용하였다.
- capacity[u][v] : u에서 v로 갈수있는 해당 파이프의 최대 용량
- flow[u][v] : u에서 v로 갈수있는 유량. flow를 0으로 두고 Residual Network에서 augmenting path를 찾아서 계속 업데이트 해간다.
- residual capacity[u][v] : u에서 v로 유량을 보내고 남은 값. augmenting path를 구한뒤에 path의 residual capacity 중 가장 작은 값을 flow에 더해준다. (반대방향은 빼준다.) 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
#include <stdint.h>

using namespace std;

int num_edges;

int capacity[INT8_MAX][INT8_MAX] = {0};
int flow[INT8_MAX][INT8_MAX] = {0};

int main(int argc, char const *argv[])
{
    scanf("%d\n", &num_edges);

    for (int i = 0; i < num_edges; i++)
    {
        char from, to;
        int cost;
        scanf("%c %c %d\n", &from, &to, &cost);

        if (from == to)
            continue;

        capacity[from][to] += cost;
        capacity[to][from] += cost;
    }

    int answer = 0;
    bool isNoAugmentPath = false;

    while (!isNoAugmentPath)
    {
        deque<char> queue = {'A'};
        int parent[INT8_MAX] = {0};
        bool isVisited[INT8_MAX] = {false};
        isVisited['A'] = true;
        isNoAugmentPath = true;

        // DFS로 augmenting path 찾기
        while (!queue.empty())
        {
            char u = queue.front();
            queue.pop_front();

            // 목적지 Z가 아니라면
            if (u != 'Z')
            {
                for (int v = 0; v < INT8_MAX; v++)
                {
                    if (capacity[u][v] - flow[u][v] > 0 && isVisited[v] == false)
                    {
                        queue.push_back(v);
                        parent[v] = u;
                        isVisited[v] = true;
                    }
                }
            }
            // 목적지 Z에 도달했다면
            else
            {
                isNoAugmentPath = false;

                // min augment를 찾는다.
                int min_augment = INT32_MAX;
                char index = 'Z';
                while (index != 'A')
                {
                    int pred = parent[index];
                    min_augment = min(min_augment, capacity[pred][index] - flow[pred][index]);
                    index = pred;
                }
                answer += min_augment;

                index = 'Z';
                while (index != 'A')
                {
                    int pred = parent[index];
                    flow[pred][index] = flow[pred][index] + min_augment;
                    flow[index][pred] = flow[index][pred] - min_augment;
                    index = pred;
                }
                break;
            }
        }
    }

    printf("%d", answer);

    return 0;
}