BOJ 6086 최대 유량

LONGNEW·2021년 12월 28일
0

BOJ

목록 보기
278/333

https://www.acmicpc.net/problem/6086
시간 1초, 메모리 128MB

input :

  • N (1 ≤ N ≤ 700)
  • 이름(알파벳 대문자 또는 소문자), 이름, 용량

output :

  • A에서 Z까지의 최대 유량을 출력

조건 :

  • 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다.

  • 병렬로 연결돼 있는 배수관들은 각 용량의 합

  • 파이프는 양방향으로 흐를 수 있다


ford fulkerson 방법으로 해결하였다.
우선적으로 병렬로 연결되어 있으면 용량을 합치기 때문에 value를 계속 초기화하는 것이 아닌 더해줘야 한다.
양방향이기 떄문에 유량을 2개 동시에 흐르도록 초기화 한다.

bfs를 수행할 때도 추가적인 방법으로 흐를 수 있는 유량이 존재하는지 판단해야 한다.

초기화를 하는 과정이 제일 복잡하니 이 부분을 잘 해야 할 것 같다.

import sys
from collections import deque

def bfs():
    visit = dict()
    for key in graph.keys():
        visit[key] = 0

    visit["A"] = 1
    q = deque(["A"])

    while q:
        node = q.popleft()

        if node == "Z":
            return True

        for next_node in graph[node]:
            if not visit[next_node] and value[node][next_node] > 0:
                visit[next_node] = 1
                prev[next_node] = node
                q.append(next_node)

    return False

def ford():
    ret = 0

    while bfs():
        min_flow, temp = float('inf'), "Z"
        while temp != "A":
            min_flow = min(min_flow, value[prev[temp]][temp])
            temp = prev[temp]

        temp = "Z"
        while temp != "A":
            value[prev[temp]][temp] -= min_flow
            value[temp][prev[temp]] += min_flow
            temp = prev[temp]

        ret += min_flow
    return ret

n = int(sys.stdin.readline())
graph, value, prev = dict(), dict(), dict()

for _ in range(n):
    a, b, c = sys.stdin.readline().split()
    c = int(c)

    if a not in value:
        graph[a] = []
        value[a] = dict()

    if b not in value:
        graph[b] = []
        value[b] = dict()

    graph[a].append(b)
    graph[b].append(a)

    if a not in value[b]:
        value[b][a] = 0
    if b not in value[a]:
        value[a][b] = 0

    value[b][a] += c
    value[a][b] += c

print(ford())

0개의 댓글