Funcia
Lv.4dinicgraphmax-flow

송수관 최대 유량

메모리 제한
256 MB
정확성 시간 제한
20000 ms
푼 사람
0
0

도시의 수도 시설 n곳(0~n-1)이 한 방향 송수관으로 이어져 있습니다. edges[i] = [u, v, c]는 시설 u에서 v로 초당 최대 c톤의 물을 보낼 수 있는 관입니다. 같은 두 시설 사이에 관이 여러 개 있을 수도 있고, 반대 방향 관이 따로 있을 수도 있습니다.

정수장 source에서 물을 내보내 배수지 sink로 모으려고 합니다. 중간 시설에서는 물이 고이거나 새지 않습니다(들어온 양 = 나간 양). 관마다 용량 이하로만 흘려보낼 때, sink에 초당 도착할 수 있는 물의 최대량을 반환하세요.

입출력 예

nedgessourcesinkresult
4[[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]]035
3[[0, 1, 5], [2, 1, 5]]020
4[[0, 1, 1000000000], [1, 2, 1], [0, 2, 1000000000], [1, 3, 1000000000], [2, 3, 1000000000]]032000000000

입출력 예 설명

예 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

제한 사항

  • 2≤2 \le n ≤10,000\le 10{,}000
  • 0≤0 \le edges.length ≤100,000\le 100{,}000
  • edges[i] = [u, v, c], 0≤u,v<0 \le u, v < n, u≠vu \ne v, 1≤c≤1091 \le c \le 10^9
  • 0≤0 \le source, sink << n, source ≠\ne sink
  • 답이 32비트 정수 범위를 넘을 수 있습니다.

기대 복잡도

시간
O(V^2 E) worst case, O(E sqrt(V)) on unit networks (Dinic)
공간
O(V + E)

입출력 예

nedgessourcesink기대 출력
4[[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]]035
3[[0,1,5],[2,1,5]]020
4[[0,1,1000000000],[1,2,1],[0,2,1000000000],[1,3,1000000000],[2,3,1000000000]]032000000000

힌트

힌트

최대 유량의 기본 — 증가 경로와 잔여 그래프

관마다 "남은 용량" 간선과, 이미 흘린 양만큼 되돌릴 수 있는 역방향 간선을 둔 잔여 그래프를 만듭니다. source에서 sink까지 남은 용량이 양수인 경로(증가 경로)를 찾아 그 경로의 최소 용량만큼 흘리기를, 경로가 없을 때까지 반복하면 최대 유량이 됩니다. 역방향 간선이 있어야 앞서 잘못 흘린 물을 다른 길로 돌릴 수 있습니다(예 1의 1 → 2).

증가 경로를 하나씩 BFS로 찾는 방법(에드몬드-카프)은 경로 수가 많을 때 BFS를 그만큼 반복하므로 효율성 테스트를 넘기 어렵습니다.

디닉(Dinic) 알고리즘

  1. BFS로 source로부터의 거리 level을 구합니다. sink에 닿지 않으면 끝입니다.
  2. level이 정확히 1 증가하는 간선만 쓰는 레벨 그래프에서, DFS로 더 이상 경로가 없을 때까지 유량을 밀어 넣습니다(차단 유량). 정점마다 "다음에 볼 간선" 포인터를 두어, 막힌 간선을 다시 보지 않게 하는 것이 핵심입니다.
  3. 1로 돌아갑니다. 단계가 반복될 때마다 sink까지의 거리가 늘어나므로 단계 수는 O(V)O(V), 용량이 1인 네트워크에서는 O(V)O(\sqrt{V}) 수준입니다.

용량 합은 32비트를 넘을 수 있으니 64비트 정수를 쓰고, 깊은 재귀가 걱정되면 DFS를 반복문으로 구현하세요.

복잡도 목표

디닉 알고리즘이면 충분합니다. 증가 경로마다 그래프 전체를 다시 BFS하는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)518 ms추정
C++ (GCC, gnu++23)518 ms도출됨
Python 3.137048 ms도출됨
Java 252038 ms도출됨
Kotlin 2.4 (JVM)2036 ms추정
C# 14 (.NET 10)2036 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance605판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.