송수관 최대 유량
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 20000 ms
- 푼 사람
- 0
도시의 수도 시설 n곳(0~n-1)이 한 방향 송수관으로 이어져 있습니다. edges[i] = [u, v, c]는 시설 u에서 v로 초당 최대 c톤의 물을 보낼 수 있는 관입니다. 같은 두 시설 사이에 관이 여러 개 있을 수도 있고, 반대 방향 관이 따로 있을 수도 있습니다.
정수장 source에서 물을 내보내 배수지 sink로 모으려고 합니다. 중간 시설에서는 물이 고이거나 새지 않습니다(들어온 양 = 나간 양). 관마다 용량 이하로만 흘려보낼 때, sink에 초당 도착할 수 있는 물의 최대량을 반환하세요.
입출력 예
| n | edges | source | sink | result |
|---|---|---|---|---|
4 | [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]] | 0 | 3 | 5 |
3 | [[0, 1, 5], [2, 1, 5]] | 0 | 2 | 0 |
4 | [[0, 1, 1000000000], [1, 2, 1], [0, 2, 1000000000], [1, 3, 1000000000], [2, 3, 1000000000]] | 0 | 3 | 2000000000 |
입출력 예 설명
예 1 — 0 → 1 → 3으로 2, 0 → 2 → 3으로 2, 0 → 1 → 2 → 3으로 1을 보내면 5입니다. 0에서 나가는 관의 용량 합이 5이므로 더 보낼 수 없습니다.
예 2 — 2 → 1 관은 반대 방향이라 쓸 수 없습니다.
예 3 — 답이 32비트 정수 범위를 넘을 수 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, edges: int[][], source: int, sink: int) → long
제한 사항
-
n -
edges.length edges[i] = [u, v, c],n, ,-
source,sinkn,sourcesink - 답이 32비트 정수 범위를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(V^2 E) worst case, O(E sqrt(V)) on unit networks (Dinic)
- 공간
- O(V + E)
입출력 예
| n | edges | source | sink | 기대 출력 |
|---|---|---|---|---|
4 | [[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]] | 0 | 3 | 5 |
3 | [[0,1,5],[2,1,5]] | 0 | 2 | 0 |
4 | [[0,1,1000000000],[1,2,1],[0,2,1000000000],[1,3,1000000000],[2,3,1000000000]] | 0 | 3 | 2000000000 |
힌트
힌트
최대 유량의 기본 — 증가 경로와 잔여 그래프
관마다 "남은 용량" 간선과, 이미 흘린 양만큼 되돌릴 수 있는 역방향 간선을 둔 잔여 그래프를 만듭니다. source에서 sink까지 남은 용량이 양수인 경로(증가 경로)를 찾아 그 경로의 최소 용량만큼 흘리기를, 경로가 없을 때까지 반복하면 최대 유량이 됩니다. 역방향 간선이 있어야 앞서 잘못 흘린 물을 다른 길로 돌릴 수 있습니다(예 1의 1 → 2).
증가 경로를 하나씩 BFS로 찾는 방법(에드몬드-카프)은 경로 수가 많을 때 BFS를 그만큼 반복하므로 효율성 테스트를 넘기 어렵습니다.
디닉(Dinic) 알고리즘
- BFS로
source로부터의 거리level을 구합니다.sink에 닿지 않으면 끝입니다. level이 정확히 1 증가하는 간선만 쓰는 레벨 그래프에서, DFS로 더 이상 경로가 없을 때까지 유량을 밀어 넣습니다(차단 유량). 정점마다 "다음에 볼 간선" 포인터를 두어, 막힌 간선을 다시 보지 않게 하는 것이 핵심입니다.- 1로 돌아갑니다. 단계가 반복될 때마다
sink까지의 거리가 늘어나므로 단계 수는 , 용량이 1인 네트워크에서는 수준입니다.
용량 합은 32비트를 넘을 수 있으니 64비트 정수를 쓰고, 깊은 재귀가 걱정되면 DFS를 반복문으로 구현하세요.
복잡도 목표
디닉 알고리즘이면 충분합니다. 증가 경로마다 그래프 전체를 다시 BFS하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 518 ms | 추정 |
| C++ (GCC, gnu++23) | 518 ms | 도출됨 |
| Python 3.13 | 7048 ms | 도출됨 |
| Java 25 | 2038 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 2036 ms | 추정 |
| C# 14 (.NET 10) | 2036 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 5 | 판정만 |