[백준][최대유량] 도시 왕복하기1

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/17412

17412번: 도시 왕복하기 1

 

내가 작성한 코드

import sys
from collections import defaultdict, deque

def get_data():
    read = sys.stdin.readline

    capa = defaultdict(lambda: defaultdict(lambda: 0))
    flow = defaultdict(lambda: defaultdict(lambda: 0))

    N, P = map(int, read().rstrip().split())
    for _ in range(P):
        s, e = map(int, read().rstrip().split())
        capa[s][e] += 1
        capa[e][s] = 0

    return N, capa, flow

def find_route(N, capa, flow):
    q = deque([1])
    parent = [-1] * (N + 1)
    parent[1] = -sys.maxsize

    while q and parent[2] == -1:
        s = q.popleft()

        for e in capa[s]:
            if capa[s][e] > flow[s][e] and parent[e] == -1:
                q.append(e)
                parent[e] = s

    return parent

def get_min_amount(capa, flow, parent):
    crnt = 2
    amount = sys.maxsize
    while parent[crnt] != -sys.maxsize:
        s = parent[crnt]
        e = crnt

        amount = min(amount, capa[s][e] - flow[s][e])
        crnt = parent[crnt]

    return amount

def set_amount(flow, parent, amount):
    crnt = 2
    while parent[crnt] != -sys.maxsize:
        s = parent[crnt]
        e = crnt

        flow[s][e] += amount
        flow[e][s] -= amount

        crnt = parent[crnt]

def edmond_karp(N, capa, flow):
    total = 0
    while True:
        parent = find_route(N, capa, flow)

        if parent[2] == -1:
            break

        amount = get_min_amount(capa, flow, parent)
        set_amount(flow, parent, amount)

        total += amount
    return total

N, capa, flow = get_data()
print(edmond_karp(N, capa, flow))

• 에드몬드-카프 알고리즘
  
  • 증가 경로가 있으면
  • 최소 유량만큼 각 경로에 더해주고 유량의 대칭성 처리
  • 유량의 총합 구하기

 

다른 사람이 작성한 코드

None

• 파이썬으로 작성된 코드가 보이지 않는다
  
  • 알고리즘 + 코드를 참고한 블로그

https://everenew.tistory.com/177

[네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘

 

기억해야할 것

• 최소 유량
  
  • 새로운 알고리즘을 공부함
  • 네트워크에서 트래픽 효율을 위해 필요할 듯