네트워크 유량 (Network Flow)

네트워크 유량 (Network Flow) ?

 

도입

• 네트워크를 이용해 수백 GB에 달하는 아주 큰 파일을 다운로드하는 중이라고 하자.
  • 이렇게 전송받을 자료의 양이 많을 때 우리가 관심을 갖는 부분은 서버가 보낸 패킷이 내 컴퓨터에 몇 밀리초 만에 도착하느냐가 아니라, 1초에 몇 MB의 자료를 전송받을 수 있느냐이다.
  • 네트워크를 구성하는 케이블들에는 일정한 대역폭이 있기 때문에, 단위 시간당 일정량 이상의 자료를 전송할 수 없다.
• 따라서 이렇게 큰 파일을 다운로드할 경우 최단 경로로만 1초에 1MB를 전송받는 것보다, 패킷을 여러 경로로 나누어 보내 그중 일부가 좀더 먼길을 돌아오더라도 초당 10MB를 전송받는 것이 훨씬 이득이다.
• 아래 그림 (a) 는 한 컴퓨터 네트워크의 구성을 표현하는 그래프를 보여준다.
  • 여기에서 왼쪽 끝과 오른쪽 끝의 사각형 정점 s와 t는 서버와 파일을 다운로드하는 컴퓨터를 나타내고, 원으로 그려진 정점들은 네트워크 장비를 의미한다.
  • 이때 정점들을 연결하는 간선들은 두 장비 사이를 연결하는 케이블로, 간선에 쓰인 숫자는 해당 케이블의 대역폭이다.
  • 예를 들어 (s, a) 를 연결하는 케이블은 초당 16MB의 자료를 전송할 수 있다.

유량 네트워크

• 이와 같은 그래프에서 각 경로를 따라 보낼 수 있는 초당 자료의 용량은 경로에 포함된 간선 중 가장 용량이 작은 간선에 의해 결정된다.
• 예를 들어 s-a-c-t의 경로를 따라 자료를 전송한다고 하자.
  • 경로에 포함된 첫 두 개의 케이블은 그 대역폭이 커서 초당 많은 자료를 전송할 수 있지만, c에서 t로 가는 케이블은 1초당 10MB 밖에 전송할 수 없다.
  • 따라서 이 경로를 따라서는 어떻게 하더라도 1초에 10MB 이상의 자료를 전송할 수 없다.
• 반면, 여러 개의 경로로 동시에 자료를 쪼개서 보낼 수 있다면 어떨까?
  • 그림 (b) 와 같이 자료를 보낼 수 있을 것이다.
  • 이때 s에서 t로 보낼 수 있는 자료양은 초당 17MB이다.
• 이렇게 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 흐름 혹은 유량 (Flow) 을 보낼 수 있는지를 계산하는 문제를 네트워크 유량 (Network Flow) 문제라고 부른다.

문제 유형

• 교통망에서 두 도시 사이를 이동할 수 있는 시간당 차량의 수, 송유관 네트워크에서 두 도시 사이에 보낼 수 있는 석유의 양 등 네트워크 유량은 현실 세계에서 자주 볼 수 있는 문제이다.
  • 또한 네트워크 유량은 광장히 강력한 최적화 문제로, 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는 데도 이용할 수 있다.

 

유량 네트워크

• 유량 네트워크 (Flow Network) ? - 각 간선에 용량 (Capacity) 이라는 추가 속성이 존재하는 방향 그래프
  • 이때 각 간선은 유량을 흘려보낼 수 있는 파이프 역할을 한다.
• 아래와 같이 사용할 때, 네트워크의 유량은 항상 다음 세 가지 속성을 만족해야 한다.
  • \(c(u, v)\) - 정점 u에서 v로 가는 간선의 용량
  • \(f(u, v)\) - 실제 흐르는 유량

1. 용량 제한 속성
   • \(f(u, v) \le c(u, v)\) : 가장 자명한 속성으로, 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.
2. 유량의 대칭성
   • \(f(u, v) = -f(v, u)\) : u에서 v로 유량이 흘러올 경우, v의 입장에서는 u로 음수의 유량을 보내는 것이라고 생각하도록 하자.
   • 곧 이어 살펴보겠지만, 이와 같은 대칭성은 우아한 알고리즘을 설계하는 데 큰 도움이 된다.
3. 유량의 보존
   • \(\sum_{v \in V} f(u, v) = 0\) : 이 속성은 각 정점에 들어오는 유량과 나가는 유량의 양은 정확히 같아야 함을 의미한다.
   • 유량의 대칭성에 의해 정점에 들어오는 유량은 모두 음수로 표현되므로, 한 정점에서 다른 모든 정점에 보내는 유량을 합하면 항상 0이 되어야 된다.

• 유량 네트워크에는 항상 특수한 두 정점 소스 (Source) & 싱크 (Sink) 가 존재한다.
  • 소스 : 유량이 시작되는 정점
  • 싱크 : 유량이 도착하는 정점
• 따라서 이 두 정점에서는 유량의 보존 속성은 성립하지 않는다.
  • 하지만 다른 모든 정점에 유량의 보존 속성이 성립해야 하기 때문에, 소스에서 나온 모든 유량은 결국 싱크로 들어가게 된다.
  • 네트워크 유량 문제는 이렇게 소스와 싱크 사이에 흐를 수 있는 최대 유량을 계산하는 문제이다.

 

 

포드-풀커슨 (Ford-Fulkerson) 알고리즘

• 포드-풀커슨 알고리즘은 최초로 고안된 네트워크 유량 알고리즘으로 그 개념과 구현이 비교적 간단하다.
  • 이보다 빠른 알고리즘도 여럿 존재하지만 대회에 출제되는 규모의 문제를 푸는 데는 큰 문제가 없으므로 대부분이 이 방법을 사용한다.

 

동작 원리

• 유량 네트워크의 모든 간선의 유량을 0으로 두고 시작해, 소스에서 싱크로 유량을 더 보낼 수 있는 경로를 찾아 유량을 보내기를 반복한다.
  • 아래 그림에서 포드-풀커슨의 동작 과정을 볼 수 있다.

포드-풀커슨 알고리즘의 동작

• 그림의 (a) 는 모든 간선의 유량이 0인 텅 빈 네트워크를 보여준다.
  • s가 소스, t가 싱크라고 할 때, 굵은 점선으로 표시된 경로를 이용하면 s에서 t로 1만큼의 추가 유량을 보낼 수 있다.
• 결과적으로 얻은 그림 (b) 에서 한번 더 굵은 점선으로 표시된 경로를 이용하면 1의 추가 유량을 t로 보내 그림 (c) 를 얻을 수 있다.
  • 이렇게 유량을 보내는 경로를 증가 경로 (Augmenting Path) 라고 부른다.
• 경로를 따라 유량을 보낼 수 있으려면 각 간선에 이미 흐르고 있는 유량 외에 추가로 유량을 보낼 수 있는 여유 용량이 있어야 한다.
  • 용량이 10인 간선에 이미 4만큼의 유량이 흐르고 있다면 이제 더 흘려보낼 수 있는 유량의 양은 6이기 때문이다.
• 앞으로는 간선의 용량과 유량의 차이를 잔여 용량 (Residual Capacity) 이라고 부르자.
  • u에서 v로 보낼 수 있는 잔여 용량 \(r(u, v)\) 를 다음과 같이 정의하자.

$$r(u, v) = c(u, v) - f(u, v)$$

• 이때 증가 경로를 통해 흘려보낼 수 있는 유량의 최대량은, 포함된 간선의 잔여 용량 중 가장 작은 값으로 결정된다.
  • 에를 들어, 위 그림 (a) 에서 (a, t) 로는 2의 유량을 더 보낼 수 있지만, (s, a) 로는 1의 유량 밖에 보낼 수 없으므로 경로 s-a-t를 통해서는 최대 1의 유량만을 보낼 수 있다.
• 포드-풀커슨은 이와 같은 증가 경로가 더이상 존재하지 않을 때까지 증가 경로를 찾고, 보낼 수 있는 최대 유량을 해당 경로를 따라 보내는 작업을 반복한다.
  • 이 증가 경로를 찾는 과정은 그래프의 탐색 알고리즘을 이용하면 쉽게 구현할 수 있다.
• 그런데 이것만으로는 아직 부족하다.
  • 이대로는 어떤 증가 경로를 선택하느냐에 따라 최대 유량을 찾을 수 없는 경우가 있기 때문이다.
• 위 그림 (a) 의 네트워크에서 증가 경로를 찾는데 s-a-t 대신 s-a-b-t가 찾아졌다고 하자.
  • 이대로 유량을 보내면 아래 그림을 얻을 수 있는데, 이제는 더이상 s에서 t로 유량을 보낼 수 없다.

유량 상쇄의 필요성

• 아직 최대 유량도 찾지 못했는데, 어떻게 해야 할까?
• 처음에 언급했던 유량의 대칭성을 돌이켜 보면 이 문제를 해결할 수 있다.
  • b에서 a로 가는 간선은 없으므로 해당 간선의 용량 c(b, a) 는 0이지만, 유량의 대칭성에 의하면 유량 f(b, a) 는 -1이다.
• 앞선 식에 따라 잔여 용량을 계산하면 아래와 같은 식인 것을 알 수 있다.

$$r(b, a) = c(b, a) - f(b, a) = 0 - (-1) = 1$$

• b에서 a로 1만큼의 유량을 보낼 수 있다는 얘기인데, 어떻게 실제로 존재하지도 않는 간선으로 유량을 보낼 수 있을까?
  • 이쪽으로 흘러오는 유량을 줄이는 것은 상대에게 유량을 보내주는 것과 같은 효과를 갖기 때문이다.
• 이와 같은 속성은 두 정점이 서로 상대에게 유량을 보내 주는 것은 의미가 없기 때문에 성립한다.

유량의 상쇄

• 위 그림 (a) 의 네트워크를 보자.
  • 이때 점선으로 표시된 간선들을 이용해 1만큼의 유량을 t로 보내면 그림 (b) 를 얻을 수 있다.
  • 이 네트워크에서는 a와 b가 서로 상대에게 1의 유량을 보내는 것을 알 수 있다.
• 어차피 1 주고 1 받는 것이니, 이 유량을 서로 상쇄해서 없애 버리면 어떨까?
  • 결과적으로 얻는 그림 (c) 에서도 우리가 지켜야 할 유량 네트워크의 세 속성은 그대로 성립한다.
  • 소스에서 싱크로 가는 총 유량도 변하지 않기 때문에, 최대 유량을 찾는 데 아무런 영향이 없다.
  • 이때 (a) 와 (c) 를 비교해 보면 b에서 a로 유량을 보내는 대신 결과적으로 a에서 b로 오는 유량을 없앤 것을 알 수 있다.
• 따라서 새 유량을 보내는 것과 기존의 유량을 상쇄하는 것은 사실상 같은 연산이라고 할 수 있다.

 

포드-풀커슨 알고리즘의 구현

• 잔여 용량이 남은 간선들만을 사용하는 BFS를 이용해 증가 경로를 찾고, 이를 따라 유량을 보내는 일을 더이상 증가 경로가 없을 때까지 반복한다.
• 아래 코드는 포드-풀커슨의 간단한 구현을 볼 수 있다.
  • NetworkFlow() 는 각 간선의 용량을 나타내는 capacity[][] 가 주어질 때, 네트워크를 따라 source에서 sink로 흘려보낼 수 있는 최대 유량을 반환한다.
  • 이때 각 간선을 따라 흐르는 유량은 flow[][] 에 저장된다.

네트워크 유량 문제를 해결하는 포드-풀커슨 알고리즘의 구현

// capacity[u][v] = u에서 v로 보낼 수 있는 용량
// flow[u][v] = u에서 v로 흘러가는 유량 (반대 방향인 경우 음수)
static int[][] capacity, flow;
static int V;
 
// flow[][] 를 계산하고 총 유량을 반환한다.
public static int NetworkFlow(int source, int sink) {
    int totalflow = 0;
 
    // flow를 0으로 초기화한다.
    for (int i = 1; i <= V; i++)
        Arrays.fill(flow[i], 0);
 
    while (true) {
        // BFS로 증가 경로를 찾는다.
        int[] parent = new int[V + 1];
        Queue<Integer> queue = new LinkedList<>();
        parent[source] = source;
        queue.offer(source);
 
        while (!queue.isEmpty() && parent[sink] == -1) {
            int from = queue.poll();
 
            for (int to = 1; to <= V; to++) {
            // 잔여 용량이 남아있는 간선을 따라 탐색한다.
                if (capacity[from][to] - flow[from][to] > 0 && parent[to] == -1) {
                    queue.offer(to);
                    parent[to] = from;
                }
            }
        }
 
        // 증가 경로가 없으면 종료한다.
        if (parent[sink] == -1)
            break;
 
        // 증가 경로를 통해 유량을 얼마나 보낼지 결정한다.
        int amount = Integer.MAX_VALUE;
 
        for (int p = sink; p != source; p = parent[p])
            amount = Math.min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
 
        // 증가 경로를 통해 유량을 보낸다.
        for (int p = sink; p != source; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
 
        totalflow += amount;
    }
 
    return totalflow;
}

• NetworkFlow() 의 내부는 커다란 무한 반복문으로 구성된다.
  • 이 반복문 내부에서는 우선 잔여 용량이 남아 있는 간선만을 이용해 BFS를 수행한다.
  • 소스에서 싱크까지의 경로를 찾아냈다면 각 간선을 검사하면서 그중 최소 잔여 용량을 찾는다.
  • 이것이 이 경로를 따라 보낼 수 있는 최대 유량이 된다.
• 그 후에는 각 간선의 유량을 갱신하는데, 유량의 대칭성을 유지하기 위해 한 방향의 유량을 늘리면 다른 방향의 유량은 줄이는 점을 눈여겨보자.

 

정당성의 증명과 최소 컷 최대 유량 정리

• 포드-풀커슨의 동작 방식은 이해하기 쉽지만, 그 정당성은 그렇게 직관적으로 와닿지 않는다.
  • 물론 최대 유량을 구하는 것이니, 유량을 보낼 수 있는 한 최대로 보내야 한다.
• 하지만 증가 경로가 여러 개인 경우 그중 아무것이나 택해도 괜찮을까?
  • 증가 경로를 잘못 택할 경우, 최대 유량을 찾기 전에 막혀서 더 증가 경로를 찾지 못하게 되는 일은 없을까?
• 이와 같은 경우가 없다는 것을 증명하는 정리가 바로 최소 컷 최대 유량 정리 (Min-cut Max-flow Theorem) 이다.
  • 이 정리는 단순히 포드-풀커슨의 정당성을 보이는 것만이 아니라 최대 유량 문제와 최소 컷 문제가 밀접하게 연관되어 있음을 보인다.
• 최소 컷 문제를 설명하기 위해 우선 컷 (Cut) 이라는 개념을 소개하겠다.
  • 유량 네트워크의 컷 ? - 소스와 싱크가 각각 다른 집합에 속하도록 그래프의 정점들을 두 개의 집합으로 나눈 것이다.
  • 이때 소스가 속한 집합을 S, T의 용량이라고 정의하고, S에서 T로 실제로 보내는 총 유량을 컷 S, T의 유량이라고 정의한다.

유량 네트워크의 소스-싱크 컷

• 위 그림에서 컷의 예를 볼 수 있다.
  • 회색 음영으로 표시된 정점들을 S, 나머지 정점들을 T라고 두면 컷 S, T의 용량은 (a, c), (b, c), (d, t) 의 용량을 더한 20 + 7 + 8 = 35이고, 그 유량은 (a, c), (b, c), (c, b), (d, t) 의 유량을 더한 13 + 0 - 3 + 7 = 17이 된다.
  • 컷의 유량은 S에서 T로 보내는 총 유량이기 때문에, T에서 S로 흘러오는 (c, b) 간선의 유량은 음수로 계산된 것을 눈여겨보자.
• 이때 유량 네트워크의 모든 컷의 유량과 용량에는 다음 두 속성이 항상 성립한다.
  • 이들은 비교적 직관적으로 이해할 수 있으므로 엄밀한 증명은 생략한다.

1. 컷의 유량은 소스에서 싱크로 가는 총 유량과 같은 것이다.
   • 네트워크의 모든 유량은 S에 포함된 소스에서 흘러나와 T에 포함된 싱크로 흘러들어가기 때문이다.
   • T에서 S로 흘러오는 유량은 음수로 계산되므로, 유량의 일부가 S와 T를 여러 번 오가는 경우에도 컷의 유량에는 한 번만 포함된다.
2. 컷의 유량은 용량과 같거나 더 작을 것이다.
   • 모든 간선에 대해 유량은 용량 이하의 값이기 때문이다.

• 다시 말하면 모든 컷의 유량은 같고, 어떤 컷에서라도 용량은 유량 이상의 값이라는 이야기다.
  • 이때 네트워크에서 용량이 가장 작은 것을 찾아내는 문제를 최소 컷 (Min cut) 문제라고 부른다.
• 최소 컷 문제는 최대 유량과 밀접하게 연관되어 있다.
  • 만약 네트워크에 용량과 유량이 같은 컷 S', T' 가 존재한다고 하자.
  • 이때 S', T'는 항상 최소 컷이며, 현재 소스에서 싱크로 보내는 유량은 네트워크의 최대 유량임을 보일 수 있다.
  • S', T' 보다 용량이 작은 컷이 존재한다면 해당 컷에 대해 유량이 용량보다 크므로 모순이고, 이보다 많은 유량을 보내는 방법이 있을 경우 S', T'에 대해 유량이 용량보다 크므로 모순이기 때문이다.
• 최소 용량 최대 유량 정리는 증가 경로가 존재하지 않는 유량 네트워크에서 용량과 유량이 같은 컷을 찾아내는 방법을 보여준다.
  • 비결은 소스에서 잔여 용량이 있는 간선을 통해 갈 수 있는 정점들의 집합 S와 그럴 수 없는 정점 T로 정점의 집합을 나누는 것이다.
• 이와 같은 분류에서 소스는 항상 S에 속할 것이고, 증가 경로가 존재하지 않기 때문에 싱크는 항상 T에 속할 것이다.
  • 따라서 S, T는 유량 네트워크의 컷이 된다.
• 이제 S에 속한 정점에서 T에 속한 정점으로 가는 모든 간선의 잔여 용량은 0이다.
  • 잔여 용량이 1이라도 있다면 반대쪽 정점 또한 S에 포함되어야 하기 때문이다.
  • 이 말은 모든 간선에 대해 용량과 유량이 같다는 뜻이므로, 이 컷은 우리가 원하는 용량과 유량이 같은 컷이 된다.
• 포드-풀커슨은 유량 네트워크에 증가 경로가 더이상 존재하지 않을 때 종료하므로, 이 과정에서 찾아낸 유량은 네트워크의 최대 유량이 된다.
  • 이렇게 최소 컷 최대 유량 정리는 포드-풀커슨의 정당성을 증명함과 동시에, 같은 알고리즘을 이용해 최소 컷 문제도 풀 수 있음을 보여준다.

 

시간 복잡도와 탐색 알고리즘의 선택

• 위 코드의 시간 복잡도를 계산하기란 꽤 까다롭다.
  • NetworkFlow()이 무한 반복문은 증가 경로를 더이상 찾지 못할 때까지 반복해서 수행되는데, 최대 유량에 도달하기 위해 증가 경로를 몇 번이나 찾아야 할지 미리 예측하기 어렵기 때문이다.
• 한 가지 방법은 증가 경로를 하나 찾을 때마다 전체 유량이 최소 1만큼은 증가한다는 점을 이용하는 것이다.
  • 따라서 최대 유량 \(f\)에 대해 증가 경로는 많아 봐야 \(f\)번 찾게 된다.
  • 여기에 그래프의 탐색에 드는 \(O(|V| + |E|)\) 를 곱하면 전체 \(O(|E|f)\) 의 시간이 걸린다는 결론을 얻을 수 있다.
• 지금까지 든 예제처럼 최대 유량이 작은 경우라면 상관 없겠지만, 최대 유량이 큰 경우 이 시간 복잡도는 문제가 될 수 있다.
  • 예를 들어 아래 그림 (a) 와 같은 네트워크가 있다고 하자.
  • 증가 경로 s-a-t와 s-b-t를 사용하면 1000만큼의 유량을 각각 보내 최대 유량을 얻을 수 있다.
• 그러나 증가 경로 탐색과정에서 증가 경로 s-a-b-t가 대신 찾아졌다면 그림 (b) 처럼 단 1의 유량만을 보낼 수 있다.
  • 거기다 더해 그 다음에 s-b-a-t가 찾아질 경우 역시 1의 유량만을 보낼 수 있으며, 그림 (c) 의 유량을 얻게 된다.
  • 이런 식으로 계속하면 이 간단한 네트워크의 최대 유량을 찾는 데 2천 번이나 증가 경로를 찾아야 한다.

포드-풀커슨 알고리즘의 DFS가 문제가 되는 경우

• 우리가 이 장에서 다룬 포드-풀커슨 알고리즘의 구현은 BFS를 사용하기 때문에 항상 가장 짧은 증가 경로만을 찾고, 따라서 위 예제와 같은 일은 일어날 수 없다.
  • 구체적인 증명은 여기에서 다루지 않지만, 포드-풀커슨을 BFS를 이용해 구현할 경우 최대 \(O(|V||E|)\)개의 증가 경로만을 사용해 최대 유량을 얻을 수 있다는 사실이 알려져 있다.
  • 증가 경로를 찾기 위해 BFS를 사용하는 포드-풀커슨의 한 형태를 에드몬드-카프 (Edmonds-Karp) 알고리즘이라고도 부른다.
• 따라서 위 코드의 시간 복잡도는 \(O(|E|f)\) 와 \(O(|V||E|^{2})\) 중 작은 것이 된다.

 

인접 리스트로 포드-풀커슨 알고리즘 구현하기

• 인접 리스트를 이용해 유량 네트워크를 저장하고 싶다면 주의할 점이 있다.
• 일반적인 경우 인접 리스트에서 방향 그래프를 저장할 때는 각 간선의 시작점에만 해당 간선의 정보를 저장한다.
  • 그러나 포드-풀커슨 알고리즘을 구현할 때는 그렇게 할 수 없다.
  • 유량의 상쇄를 통해 실제 간선의 반대 방향으로도 유량을 보낼 필요가 있기 때문이다.
• 따라서 포드-풀커슨을 구현할 때는 각 단방향 간선 (u, v) 마다 용량이 0인 '유령' 간선 (v, u) 를 네트워크에 추가해 줘야 한다.
  • 이 유령 간선은 유량을 상쇄하는 데만 사용할 수 있다.
• 이때 유의할 점은 각 간선은 자신의 반대 방향 간선에 빠르게 접근할 수 있어야 한다는 것이다.
  • 한 간선의 유량을 갱신할 때 다른 한쪽의 유량도 갱신해야 하기 때문이다.
  • 한 가지 방법은 각 간선을 클래스로 표현하고, 각 간선이 반대 방향 간선을 가지고 있도록 하는 것이다.
• 이와 같은 구현의 대체적인 형태를 아래 코드에서 볼 수 있다.
  • 간선 (u, v) 를 추가할 때 반대 방향 간선 (v, u) 또한 같이 만들어 이들을 서로 연결하고, Edge::push에서 유량을 보낼 때 반대 방향의 유량도 갱신하는 것을 눈여겨보자.

// 유량 네트워크의 인접리스트 
static LinkedList<Edge>[] graph = new LinkedList[V + 1];
 
// u에서 v로 가는 간선을 추가한다.
public static void addEdge(int u, int v, int capacity) {
    Edge uvEdge = new Edge();
    Edge vuEdge = new Edge();
    
    // u에서 v로 가는 간선을 초기화 한다.
    uvEdge.target = v;
    uvEdge.capacity = capacity;
    uvEdge.flow = 0;
    uvEdge.reverse = vuEdge;
    
    // v에서 u로 가는 간선을 초기화 한다. 이 간선의 용량은 0이다.
    vuEdge.target = u;
    vuEdge.capacity = 0;
    vuEdge.flow = 0;
    vuEdge.reverse = uvEdge;
    
    graph[u].add(uvEdge);
    graph[v].add(vuEdge);
}
 
// 간선의 정보를 나타내는 클래스
public static class Edge {
    int target, capacity, flow;
 
    // 역방향 간선
    Edge reverse;
 
    // 이 간선의 잔여용량을 계산한다.
    public int residualCapacity() {
        return capacity - flow;
    }
 
    // 이 간선을 따라 용량 amt를 보낸다.
    public void push(int amt) {
        this.flow += amt;
        reverse.flow -= amt;
    }
}

 

Reference

• 도서 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략