문제 45
유량 흘리기 3
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 용량과 비용이 있는 방향 간선으로 이루어진 그래프가 있다.
시작 정점 $S$에서 도착 정점 $T$로 보낼 수 있는 유량의 최댓값과, 해당 유량을 보낼 때 필요한 비용의 최솟값을 구하라.
각 간선으로 보내는 유량은 해당 간선의 용량을 넘을 수 없으며, $S$와 $T$를 제외한 모든 정점에서는 들어오는 유량의 합과 나가는 유량의 합이 같아야 한다.
입력
첫 번째 줄에 네 정수 $N$, $M$, $S$, $T$가 공백으로 구분되어 주어진다. $(2 \le N \le 100; 0 \le M \le \min(500, \frac{N(N-1)}{2}); 1 \le S, T \le N; S \neq T)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 방향 간선의 시작 정점의 번호, 도착 정점의 번호, 용량, 단위 유량당 비용을 의미하는 네 정수 $u$, $v$, $c$, $w$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v; 1 \le c \le 100; 0 \le w \le 10^6)$
같은 두 정점을 잇는 간선은 방향과 관계없이 두 번 이상 주어지지 않는다.
출력
첫 번째 줄에 $S$에서 $T$로 보낼 수 있는 유량의 최댓값을 출력한다.
두 번째 줄에 해당 유량을 보낼 때 필요한 비용의 최솟값을 출력한다.
예제 입력 1
6 7 1 6 1 2 2 2 1 4 2 1 2 3 2 2 4 3 1 2 4 5 2 3 3 6 2 1 5 6 1 2
예제 출력 1
3 15
예제 입력 2
4 2 1 4 1 2 3 10 3 4 5 20
예제 출력 2
0 0
공식 해설
가장 싼 경로로 최대한 보내기
유량을 먼저 최대화하고, 같은 유량 중 비용을 최소화해야 한다. 유량 $0$에서 시작해 잔여 그래프의 최소 비용 $S$-$T$ 경로로 유량을 늘린다. 경로의 비용이 양수여도 보낼 수 있다면 계속 보내야 한다.
용량 $c$, 비용 $w$인 간선마다 초기 용량 $0$, 비용 $-w$인 역간선을 함께 만든다. 역간선으로 유량을 보내면 기존 유량을 취소하므로 그 비용도 돌려받는다.
잠재값으로 음수 역간선 처리하기
정점마다 잠재값 $h_v$를 두고 간선의 비용을
\[
w'(u,v)=w(u,v)+h_u-h_v
\]
로 바꾼다. 같은 두 끝점을 잇는 경로들은 비용이 모두 $h_S-h_T$만큼 변하므로 최단 경로는 바뀌지 않는다.
처음에는 사용 가능한 간선의 비용이 음수가 아니므로 모든 $h_v=0$으로 시작한다. 바꾼 비용으로 다익스트라를 수행하여 거리 $d_v$를 구한 뒤, 도달한 정점마다 $h_v\leftarrow h_v+d_v$로 갱신한다.
최단 거리의 성질 $d_v\le d_u+w'(u,v)$ 때문에 새 잔여 비용은 음수가 아니다. 최단 경로의 간선은 새 비용이 $0$이므로, 유량을 보내며 열리는 역간선의 새 비용도 $0$이다. 따라서 다음 단계에도 다익스트라를 쓸 수 있다. 이번에 도달하지 못한 정점은 증강으로 새로 열리는 역간선의 끝점이 될 수 없으므로 다음 탐색에 필요한 성질도 유지된다.
유량과 비용 갱신하기
경로의 최소 잔여 용량을 $\Delta$라 하자. 각 간선과 역간선의 잔여 용량을 갱신하고, 총유량에 $\Delta$, 총비용에 경로의 원래 비용 합을 $\Delta$배 한 값을 더한다.
최소 비용 증강은 현재 유량을 더 싸게 재배치할 음수 비용 사이클을 만들지 않는다. 최단 경로 간선을 따라 열린 역간선의 바뀐 비용이 $0$이고, 도달 가능한 나머지 간선의 바뀐 비용도 음수가 아니기 때문이다. 도달하지 못한 부분의 사이클은 이번 증강으로 바뀌지 않는다. 같은 유량의 두 흐름의 차는 잔여 사이클들로 나뉘므로, 음수 사이클이 없다는 것은 현재 유량에서 비용이 최소라는 뜻이다.
$T$에 도달할 수 없으면 더 보낼 경로가 없으므로 최대 유량이며, 그 유량의 최소 비용도 얻었다.
증강 횟수를 $A$라 하면 시간복잡도는 $O((A+1)(N+M)\log N)$, 공간복잡도는 $O(N+M)$이다. 용량이 정수이므로 $A$는 최대 유량 이하이다. 총비용은 각 간선의 유량과 비용을 곱한 값들의 합이므로 이 곱과 누적합을 정확히 계산해야 한다.
구현 · 언어별 풀이
C++ 구현
간선 구조체에 도착점·잔여 용량·비용·역간선 인덱스를 저장한다. 거리와 잠재값, 총비용은 long long으로 두고 다익스트라의 힙은 greater<> 비교자를 사용한다. 잠재값은 유한한 거리를 얻은 정점에만 더한다. 비용은 경로의 원래 비용과 보낸 유량의 곱으로 누적한다.
C 구현
잔여 간선에 long long 비용과 용량을 저장한다. potential을 사용한 Dijkstra에는 최소 힙이 필요하다. 역간선 비용은 음수이며 경로 비용에 증가 유량을 곱해 long long 총비용에 더한다.
Python 구현
heapq와 정수 dist/potential 배열로 reduced cost Dijkstra를 구현한다. 도달한 정점의 potential만 갱신한다. 경로 비용은 원래 간선 비용으로 합하고 증가 유량과 곱하여 누적한다.
Java 구현
비용·거리·potential과 총비용은 long으로 둔다. PriorityQueue의 거리 비교는 Long.compare를 사용한다. 역간선 비용 부호를 뒤집고 유한한 거리의 정점만 potential을 갱신한다.
Rust 구현
간선 비용과 potential은 i64이며 최소 힙은 BinaryHeap<Reverse<(i64,usize)>>로 둔다. 잔여 용량을 정·역방향 모두 갱신하고 전체 비용에는 원래 비용의 경로 합을 곱한다.
JavaScript 구현
잠재값·거리·원래 비용·총비용은 Number로 둘 수 있다. 최종 총비용은 모든 입력 간선의 용량과 비용 곱의 합 이하인 $500\cdot100\cdot10^6=5\cdot10^{10}$이고 경로 비용·잠재값도 안전 정수 범위 안이다.
잔여 간선마다 목적지, 역간선 인덱스, 용량, 비용을 저장하고 역방향 비용은 부호를 바꾼다. 최소 이진 힙에서 reduced cost 거리로 후보를 비교한다. 도달한 정점의 잠재값만 갱신하고 비용 누적에는 경로의 원래 비용을 사용한다. 싼 유량만 보내다 멈추지 말고, 경로가 있는 한 양수 비용도 보내야 최대 유량의 최소 비용이 된다.