문제 44
유량 흘리기 1
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 용량이 있는 방향 간선으로 이루어진 그래프가 있다.
시작 정점 $S$에서 도착 정점 $T$로 보낼 수 있는 유량의 최댓값을 구하라.
각 간선으로 보내는 유량은 해당 간선의 용량을 넘을 수 없으며, $S$와 $T$를 제외한 모든 정점에서는 들어오는 유량의 합과 나가는 유량의 합이 같아야 한다.
입력
첫 번째 줄에 네 정수 $N$, $M$, $S$, $T$가 공백으로 구분되어 주어진다. $(2 \le N \le 100; 0 \le M \le 500; 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
공식 해설
보낸 유량을 되돌릴 수 있게 만들기
현재 더 보낼 수 있는 양을 잔여 용량이라고 하자. 입력 간선마다 원래 용량을 가진 정방향 간선과 초기 잔여 용량이 $0$인 역방향 간선을 한 쌍으로 만든다. 정방향으로 $\Delta$를 보내면 그 잔여 용량을 줄이고 짝인 역방향의 잔여 용량을 늘린다.
역방향 간선은 이미 보낸 유량을 취소하여 다른 경로로 바꿀 수 있게 한다. 반대 방향의 원래 간선도 입력되었다면 별도의 간선 쌍으로 저장한다.
BFS로 증강 경로 찾기
잔여 용량이 양수인 간선만 따라 BFS하여 $S$에서 $T$로 가는 경로를 찾는다. 경로가 있으면 그 위의 최소 잔여 용량만큼 유량을 보내고, 보낸 양을 답에 더한다. 이것이 에드몬즈–카프 알고리즘이다.
경로가 더 이상 없으면 잔여 그래프에서 $S$로부터 도달하는 정점들을 모은다. $T$는 이 집합 밖에 있고, 집합 밖으로 더 보낼 잔여 용량도 없다. 현재 유량은 이 경계를 가로지르는 컷의 용량에 도달한 것이다. 어떤 유량도 컷의 용량을 넘을 수 없으므로 현재 값이 최대이다.
인접 리스트와 역간선 인덱스를 사용하면 시간복잡도는 $O(N+M+NM^2)$, 공간복잡도는 $O(N+M)$이다. 총유량은 여러 간선으로 보낸 양의 합이므로 개별 간선의 용량 범위로 제한하지 않는다.
구현 · 언어별 풀이
C++ 구현
간선 구조체에 도착 정점, 잔여 용량, 짝인 역간선의 인덱스를 저장한다. BFS에서는 부모 정점뿐 아니라 사용한 간선의 인덱스도 기록해야 경로를 정확히 복원할 수 있다. 잔여 용량과 총유량은 long long으로 관리한다.
C 구현
정·역방향 간선을 연속 두 칸에 넣으면 역간선 인덱스가 e^1이다. BFS에 부모 간선 번호를 저장하고 경로를 따라 용량을 갱신한다. 용량과 전체 유량은 long long으로 둔다.
Python 구현
각 간선의 목적지·역간선 위치·잔여 용량을 저장한다. BFS에서 부모 간선을 기억해 최소 잔여 용량을 구하고 두 방향을 함께 갱신한다. 반대 방향의 원래 간선과 역간선을 같은 항목으로 덮어쓰지 않는다.
Java 구현
잔여 간선을 쌍으로 저장하고 BFS의 parent에는 정점만이 아니라 간선 번호를 넣는다. 합 유량은 long이며, 역간선 용량 증가를 빠뜨리지 않는다.
Rust 구현
잔여 간선을 Vec에 연속 두 칸씩 추가한다. e와 e^1의 용량을 순서대로 바꾸면 동시에 두 가변 참조를 얻을 필요가 없다. BFS 큐는 VecDeque이며 전체 유량은 i64다.
JavaScript 구현
역간선의 위치를 함께 저장하는 인접 리스트로 잔여 그래프를 만든다. BFS 큐는 숫자 배열과 head 인덱스로 구현하고 부모에는 정점뿐 아니라 선택한 간선 위치도 저장한다.
용량과 총유량은 Number로 충분하다. 모든 입력 용량 합이 $M\cdot10^9\le5\cdot10^{11}$이므로 정확히 표현된다. 경로의 최소 잔여 용량을 찾고 정방향에서 빼며 그 짝 역방향에 더한다. 반대 방향의 원래 간선이 있어도 새로운 역간선 쌍과 덮어 합치지 않는다.