문제 46
유량 흘리기 2
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 용량이 있는 방향 간선으로 이루어진 그래프가 있다.
시작 정점 $S$에서 도착 정점 $T$로 보낼 수 있는 유량의 최댓값을 구하라.
각 간선으로 보내는 유량은 해당 간선의 용량을 넘을 수 없으며, $S$와 $T$를 제외한 모든 정점에서는 들어오는 유량의 합과 나가는 유량의 합이 같아야 한다.
입력
첫 번째 줄에 네 정수 $N$, $M$, $S$, $T$가 공백으로 구분되어 주어진다. $(2 \le N \le 2\,000; 0 \le M \le 500\,000; 1 \le S, T \le N; S \neq T)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 방향 간선의 시작 정점의 번호, 도착 정점의 번호, 용량을 의미하는 세 정수 $u$, $v$, $c$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v; 1 \le c \le 10^9)$
같은 방향 간선은 두 번 이상 주어지지 않는다.
출력
$S$에서 $T$로 보낼 수 있는 유량의 최댓값을 출력한다.
예제 입력 1
6 7 1 6 1 2 3 1 3 2 2 4 2 2 5 1 3 4 1 4 6 3 5 6 1
예제 출력 1
4
예제 입력 2
4 2 1 4 1 2 10 3 4 10
예제 출력 2
0
공식 해설
간선이 최대 $500\,000$개이므로 증강 경로 하나마다 BFS를 새로 하는 대신, 같은 최단 거리의 경로들을 한 단계에 묶어 처리한다.
같은 길이의 증강 경로들을 한 번에 처리하기
간선마다 잔여 용량과 역간선의 인덱스를 저장하는 Dinic 알고리즘을 사용한다. 입력 간선마다 초기 용량 $0$인 역간선을 별도로 만들어, 이미 보낸 유량도 취소할 수 있게 한다.
먼저 잔여 용량이 양수인 간선으로 BFS하여 $S$에서의 거리를 레벨로 정한다. 다음에는 레벨이 정확히 $1$ 증가하는 간선만 따라 DFS로 유량을 보낸다. 경로마다 가능한 최소 잔여 용량을 보내고 역간선의 잔여 용량도 함께 갱신한다.
한 정점에서 더 보낼 수 없었던 간선을 같은 단계에서 다시 보지 않도록 다음에 확인할 간선 위치를 저장한다. 같은 레벨 그래프에서 $S$-$T$ 경로가 더는 남지 않을 때까지 보내면 차단 유량을 얻는다. 이후 BFS로 레벨을 새로 구해 반복한다.
한 단계가 끝나면 이전의 최단 증강 경로들은 모두 막혔으므로 다음 증강 경로의 길이는 더 길어진다. 레벨이 증가하는 간선만 따라가므로 DFS 중 사이클을 돌지도 않는다.
BFS에서 $T$에 도달할 수 없으면 잔여 증강 경로가 없으므로 현재 유량이 최대이다. 이때 $S$에서 도달 가능한 정점들이 최대 유량과 용량이 같은 컷을 이룬다.
일반적인 시간복잡도는 $O(N+M+N^2M)$이고, 인접 리스트를 사용한 공간복잡도는 $O(N+M)$이다. 총유량은 여러 간선으로 보낸 양의 합이므로 개별 간선의 용량 범위로 제한하지 않는다.
구현 · 언어별 풀이
C++ 구현
vector 기반 인접 리스트와 역간선 인덱스를 사용한다. 레벨과 현재 간선 위치를 배열에 저장하고, 현재 간선 위치는 BFS로 새 레벨 그래프를 만들 때만 초기화한다. 용량과 DFS가 반환하는 유량, 총유량은 모두 long long으로 맞춘다.
C 구현
최대 백만 개의 잔여 간선은 연속 배열로 저장한다. BFS level과 DFS current arc를 분리하고 BFS 단계마다 current arc를 초기화한다. 용량 합은 long long이며 긴 경로에는 명시적 DFS 스택을 사용할 수 있다.
Python 구현
잔여 간선은 to/next/용량의 평탄 배열로 저장하면 백만 개의 간선 객체 비용을 줄인다. level BFS 뒤 current arc로 blocking flow를 찾는다. 깊이 2000의 경로에서 기본 재귀 한도에 의존하지 않도록 DFS 스택으로 경로를 관리한다.
Java 구현
to/next는 int[], 용량은 long[]로 두면 많은 간선의 객체 할당을 피한다. level BFS와 current arc를 사용하며 긴 증가 경로는 반복 DFS로 처리할 수 있다. 전체 유량은 long이다.
Rust 구현
Vec에 정·역방향 간선을 쌍으로 저장하고 level, current arc를 별도로 둔다. i64로 유량 합을 계산한다. DFS에서 간선 정보를 복사한 뒤 호출·갱신하면 borrow 충돌을 피할 수 있다.
JavaScript 구현
최대 백만 개의 정·역간선을 객체로 만들기보다 목적지·다음 간선·head를 Int32Array, 잔여 용량을 Float64Array로 저장하면 메모리를 줄일 수 있다. 간선을 두 개씩 연속 등록하면 역간선 인덱스는 e ^ 1이다. 이 비트 연산의 대상은 간선 번호이지 용량이 아니다.
모든 용량 합은 $5\cdot10^{14}$ 이하이므로 Number로 정확하다. 레벨 BFS는 head/tail 큐를 쓰고, 차단 유량 탐색에는 현재 간선 위치와 명시적 경로 스택을 사용하면 긴 경로에서 JavaScript 호출 스택에 의존하지 않는다. 실패한 간선을 같은 레벨 단계에서 다시 검사하지 않도록 current arc를 유지한다.