import sys,collections
def input(): return map(int,sys.stdin.readline().split())
def BFS():
dq = collections.deque([0])
parent = [-1]*N
while dq:
now = dq.popleft()
for next in adj[now]:
if graph[now][next]-flow[now][next] and parent[next]<0:
parent[next] = now
dq.append(next)
if next==N-1:
return parent
def solve():
while parent:=BFS():
now = N-1; f = 3**M
while now:
last = parent[now]
f = min(f,graph[last][now]-flow[last][now])
now = last
now = N-1
while now:
last = parent[now]
flow[last][now] += f; flow[now][last] -= f
now = last
N,M = input()
graph = [[0]*N for i in range(N)]; adj = [[] for i in range(N)]
for i in range(M):
a,b = input()
adj[a].append(b); adj[b].append(a)
graph[a][b] = graph[b][a] = 3**i
flow = [[0]*N for i in range(N)]
solve()
print(sum(flow[i][-1] for i in range(N))%(10**9+7))
최대유량으로 해결하였다.
그냥 최대유량 알고리즘을 이용하면 쉽게 답을 구할 수 있다. M개의 양방향 간선에 대해 각 용량을 3^i로 두면 된다.
하지만 이 문제는 그리디한 방법으로 더 빠르게 해결할 수 있다고 하니 그 방법도 생각해봐야겠다.
예상컨대 3^i > 3^0+3^1+3^2+ ... + 3^(i-1)인 점을 이용하지 않을까 생각한다.
오늘의 교훈) 그리디한 방법으로도 문제를 해결해보자