25_network_flow.py

  1"""
  2네트워크 플로우 (Network Flow)
  3Maximum Flow and Bipartite Matching
  4
  5그래프에서 최대 유량을 구하는 알고리즘입니다.
  6"""
  7
  8from typing import List, Tuple, Dict
  9from collections import defaultdict, deque
 10
 11
 12# =============================================================================
 13# 1. Ford-Fulkerson (DFS 기반)
 14# =============================================================================
 15
 16def ford_fulkerson(capacity: List[List[int]], source: int, sink: int) -> int:
 17    """
 18    Ford-Fulkerson 알고리즘 (DFS)
 19    시간복잡도: O(E * max_flow)
 20    """
 21    n = len(capacity)
 22    residual = [row[:] for row in capacity]
 23
 24    def dfs(node: int, flow: int, visited: List[bool]) -> int:
 25        if node == sink:
 26            return flow
 27
 28        visited[node] = True
 29
 30        for next_node in range(n):
 31            if not visited[next_node] and residual[node][next_node] > 0:
 32                min_flow = min(flow, residual[node][next_node])
 33                result = dfs(next_node, min_flow, visited)
 34
 35                if result > 0:
 36                    residual[node][next_node] -= result
 37                    residual[next_node][node] += result
 38                    return result
 39
 40        return 0
 41
 42    max_flow = 0
 43    while True:
 44        visited = [False] * n
 45        flow = dfs(source, float('inf'), visited)
 46        if flow == 0:
 47            break
 48        max_flow += flow
 49
 50    return max_flow
 51
 52
 53# =============================================================================
 54# 2. Edmonds-Karp (BFS 기반)
 55# =============================================================================
 56
 57def edmonds_karp(capacity: List[List[int]], source: int, sink: int) -> int:
 58    """
 59    Edmonds-Karp 알고리즘 (BFS)
 60    시간복잡도: O(V * E²)
 61    """
 62    n = len(capacity)
 63    residual = [row[:] for row in capacity]
 64
 65    def bfs() -> List[int]:
 66        """BFS로 증가 경로 찾기"""
 67        parent = [-1] * n
 68        visited = [False] * n
 69        visited[source] = True
 70        queue = deque([source])
 71
 72        while queue:
 73            node = queue.popleft()
 74
 75            for next_node in range(n):
 76                if not visited[next_node] and residual[node][next_node] > 0:
 77                    visited[next_node] = True
 78                    parent[next_node] = node
 79                    queue.append(next_node)
 80
 81                    if next_node == sink:
 82                        return parent
 83
 84        return parent
 85
 86    max_flow = 0
 87
 88    while True:
 89        parent = bfs()
 90
 91        if parent[sink] == -1:
 92            break
 93
 94        # 경로의 최소 용량 찾기
 95        path_flow = float('inf')
 96        node = sink
 97        while node != source:
 98            prev = parent[node]
 99            path_flow = min(path_flow, residual[prev][node])
100            node = prev
101
102        # 잔여 그래프 업데이트
103        node = sink
104        while node != source:
105            prev = parent[node]
106            residual[prev][node] -= path_flow
107            residual[node][prev] += path_flow
108            node = prev
109
110        max_flow += path_flow
111
112    return max_flow
113
114
115# =============================================================================
116# 3. Dinic 알고리즘
117# =============================================================================
118
119class Dinic:
120    """
121    Dinic 알고리즘
122    시간복잡도: O(V² * E)
123    이분 그래프에서: O(E * √V)
124    """
125
126    def __init__(self, n: int):
127        self.n = n
128        self.graph = defaultdict(list)
129
130    def add_edge(self, u: int, v: int, cap: int):
131        """간선 추가 (u → v, 용량 cap)"""
132        # (인접 노드, 잔여 용량, 역방향 간선 인덱스)
133        self.graph[u].append([v, cap, len(self.graph[v])])
134        self.graph[v].append([u, 0, len(self.graph[u]) - 1])
135
136    def bfs(self, source: int, sink: int) -> bool:
137        """레벨 그래프 구성"""
138        self.level = [-1] * self.n
139        self.level[source] = 0
140        queue = deque([source])
141
142        while queue:
143            node = queue.popleft()
144            for next_node, cap, _ in self.graph[node]:
145                if cap > 0 and self.level[next_node] < 0:
146                    self.level[next_node] = self.level[node] + 1
147                    queue.append(next_node)
148
149        return self.level[sink] >= 0
150
151    def dfs(self, node: int, sink: int, flow: int) -> int:
152        """blocking flow 찾기"""
153        if node == sink:
154            return flow
155
156        for i in range(self.iter[node], len(self.graph[node])):
157            self.iter[node] = i
158            next_node, cap, rev = self.graph[node][i]
159
160            if cap > 0 and self.level[next_node] == self.level[node] + 1:
161                d = self.dfs(next_node, sink, min(flow, cap))
162
163                if d > 0:
164                    self.graph[node][i][1] -= d
165                    self.graph[next_node][rev][1] += d
166                    return d
167
168        return 0
169
170    def max_flow(self, source: int, sink: int) -> int:
171        """최대 유량 계산"""
172        flow = 0
173
174        while self.bfs(source, sink):
175            self.iter = [0] * self.n
176
177            while True:
178                f = self.dfs(source, sink, float('inf'))
179                if f == 0:
180                    break
181                flow += f
182
183        return flow
184
185
186# =============================================================================
187# 4. 이분 매칭 (Bipartite Matching)
188# =============================================================================
189
190def bipartite_matching(n: int, m: int, edges: List[Tuple[int, int]]) -> int:
191    """
192    이분 그래프 최대 매칭 (Hopcroft-Karp 간소화)
193    n: 왼쪽 정점 수, m: 오른쪽 정점 수
194    edges: [(왼쪽, 오른쪽), ...]
195    시간복잡도: O(E * √V)
196    """
197    # 그래프 구성
198    adj = defaultdict(list)
199    for u, v in edges:
200        adj[u].append(v)
201
202    match_left = [-1] * n   # 왼쪽 정점의 매칭
203    match_right = [-1] * m  # 오른쪽 정점의 매칭
204
205    def dfs(u: int, visited: List[bool]) -> bool:
206        for v in adj[u]:
207            if visited[v]:
208                continue
209            visited[v] = True
210
211            # 매칭 안됨 또는 재매칭 가능
212            if match_right[v] == -1 or dfs(match_right[v], visited):
213                match_left[u] = v
214                match_right[v] = u
215                return True
216
217        return False
218
219    matching = 0
220    for u in range(n):
221        visited = [False] * m
222        if dfs(u, visited):
223            matching += 1
224
225    return matching
226
227
228# =============================================================================
229# 5. 최소 컷 (Minimum Cut)
230# =============================================================================
231
232def min_cut(capacity: List[List[int]], source: int, sink: int) -> Tuple[int, List[int]]:
233    """
234    최소 컷 = 최대 유량
235    반환: (컷 용량, source 측 정점 집합)
236    """
237    n = len(capacity)
238    residual = [row[:] for row in capacity]
239
240    # Edmonds-Karp로 최대 유량 계산
241    def bfs_flow() -> bool:
242        parent = [-1] * n
243        visited = [False] * n
244        visited[source] = True
245        queue = deque([source])
246
247        while queue:
248            node = queue.popleft()
249            for next_node in range(n):
250                if not visited[next_node] and residual[node][next_node] > 0:
251                    visited[next_node] = True
252                    parent[next_node] = node
253                    queue.append(next_node)
254
255        if parent[sink] == -1:
256            return False
257
258        path_flow = float('inf')
259        node = sink
260        while node != source:
261            prev = parent[node]
262            path_flow = min(path_flow, residual[prev][node])
263            node = prev
264
265        node = sink
266        while node != source:
267            prev = parent[node]
268            residual[prev][node] -= path_flow
269            residual[node][prev] += path_flow
270            node = prev
271
272        return True
273
274    while bfs_flow():
275        pass
276
277    # 잔여 그래프에서 source에서 도달 가능한 정점 찾기
278    visited = [False] * n
279    queue = deque([source])
280    visited[source] = True
281
282    while queue:
283        node = queue.popleft()
284        for next_node in range(n):
285            if not visited[next_node] and residual[node][next_node] > 0:
286                visited[next_node] = True
287                queue.append(next_node)
288
289    # 컷 용량 계산
290    cut_capacity = 0
291    source_side = []
292    for i in range(n):
293        if visited[i]:
294            source_side.append(i)
295            for j in range(n):
296                if not visited[j] and capacity[i][j] > 0:
297                    cut_capacity += capacity[i][j]
298
299    return cut_capacity, source_side
300
301
302# =============================================================================
303# 6. 실전 문제: 작업 할당
304# =============================================================================
305
306def assign_tasks(workers: int, tasks: int, can_do: List[List[int]]) -> List[int]:
307    """
308    작업자에게 작업 할당 (이분 매칭)
309    can_do[i] = worker i가 수행 가능한 작업 목록
310    반환: assignment[worker] = 할당된 작업 (-1이면 미할당)
311    """
312    edges = []
313    for worker, tasks_list in enumerate(can_do):
314        for task in tasks_list:
315            edges.append((worker, task))
316
317    # 이분 매칭 수행
318    adj = defaultdict(list)
319    for u, v in edges:
320        adj[u].append(v)
321
322    match_worker = [-1] * workers
323    match_task = [-1] * tasks
324
325    def dfs(u: int, visited: List[bool]) -> bool:
326        for v in adj[u]:
327            if visited[v]:
328                continue
329            visited[v] = True
330
331            if match_task[v] == -1 or dfs(match_task[v], visited):
332                match_worker[u] = v
333                match_task[v] = u
334                return True
335
336        return False
337
338    for u in range(workers):
339        visited = [False] * tasks
340        dfs(u, visited)
341
342    return match_worker
343
344
345# =============================================================================
346# 7. 실전 문제: 최대 간선 분리 경로
347# =============================================================================
348
349def max_edge_disjoint_paths(n: int, edges: List[Tuple[int, int]], source: int, sink: int) -> int:
350    """
351    간선 분리 경로의 최대 개수
352    각 간선 용량 = 1로 설정한 최대 유량
353    """
354    capacity = [[0] * n for _ in range(n)]
355
356    for u, v in edges:
357        capacity[u][v] = 1
358        capacity[v][u] = 1  # 무방향 그래프인 경우
359
360    return edmonds_karp(capacity, source, sink)
361
362
363# =============================================================================
364# 테스트
365# =============================================================================
366
367def main():
368    print("=" * 60)
369    print("네트워크 플로우 (Network Flow) 예제")
370    print("=" * 60)
371
372    # 그래프 예시:
373    #     10      10
374    #  0 ───→ 1 ───→ 3
375    #  │      │      ↑
376    #  │10    │2     │10
377    #  ↓      ↓      │
378    #  2 ───→ 4 ───→ 5
379    #     10      10
380
381    # 1. Ford-Fulkerson
382    print("\n[1] Ford-Fulkerson")
383    capacity = [
384        [0, 10, 10, 0, 0, 0],  # 0
385        [0, 0, 2, 10, 0, 0],   # 1
386        [0, 0, 0, 0, 10, 0],   # 2
387        [0, 0, 0, 0, 0, 10],   # 3
388        [0, 0, 0, 0, 0, 10],   # 4
389        [0, 0, 0, 0, 0, 0]     # 5 (sink)
390    ]
391    flow = ford_fulkerson(capacity, 0, 5)
392    print(f"    source=0, sink=5")
393    print(f"    최대 유량: {flow}")
394
395    # 2. Edmonds-Karp
396    print("\n[2] Edmonds-Karp")
397    flow = edmonds_karp(capacity, 0, 5)
398    print(f"    최대 유량: {flow}")
399
400    # 3. Dinic
401    print("\n[3] Dinic 알고리즘")
402    dinic = Dinic(6)
403    dinic.add_edge(0, 1, 10)
404    dinic.add_edge(0, 2, 10)
405    dinic.add_edge(1, 2, 2)
406    dinic.add_edge(1, 3, 10)
407    dinic.add_edge(2, 4, 10)
408    dinic.add_edge(3, 5, 10)
409    dinic.add_edge(4, 5, 10)
410    flow = dinic.max_flow(0, 5)
411    print(f"    최대 유량: {flow}")
412
413    # 4. 이분 매칭
414    print("\n[4] 이분 매칭")
415    # 왼쪽: 0, 1, 2 (작업자)
416    # 오른쪽: 0, 1, 2 (작업)
417    edges = [(0, 0), (0, 1), (1, 0), (1, 2), (2, 1)]
418    matching = bipartite_matching(3, 3, edges)
419    print(f"    간선: {edges}")
420    print(f"    최대 매칭: {matching}")
421
422    # 5. 최소 컷
423    print("\n[5] 최소 컷")
424    cut_cap, source_side = min_cut(capacity, 0, 5)
425    print(f"    최소 컷 용량: {cut_cap}")
426    print(f"    source 측 정점: {source_side}")
427
428    # 6. 작업 할당
429    print("\n[6] 작업 할당")
430    can_do = [
431        [0, 1],     # 작업자 0: 작업 0, 1 가능
432        [1, 2],     # 작업자 1: 작업 1, 2 가능
433        [0, 2]      # 작업자 2: 작업 0, 2 가능
434    ]
435    assignment = assign_tasks(3, 3, can_do)
436    print(f"    수행 가능: {can_do}")
437    print(f"    할당 결과: {assignment}")
438
439    # 7. 알고리즘 비교
440    print("\n[7] 알고리즘 복잡도 비교")
441    print("    | 알고리즘      | 시간 복잡도       | 특징               |")
442    print("    |---------------|-------------------|-------------------|")
443    print("    | Ford-Fulkerson| O(E * max_flow)   | DFS, 정수 용량     |")
444    print("    | Edmonds-Karp  | O(V * E²)         | BFS, 안정적        |")
445    print("    | Dinic         | O(V² * E)         | 레벨 그래프        |")
446    print("    | 이분 매칭     | O(E * √V)         | Dinic 특수 케이스  |")
447
448    print("\n" + "=" * 60)
449
450
451if __name__ == "__main__":
452    main()