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())
