PAST3O

https://gyazo.com/c243561fb3069ff0f7a2c41046325ef2

PAST3O

https://gyazo.com/44f1480ffab9934faa88f95412112586

考えたこと

公式解説

1,2,3回の時のコストの増分が単調増加であることが重要

3本の辺を引くことができる

https://gyazo.com/9e4af4847d4cf7c78354a6753ac9b49c

https://gyazo.com/c243561fb3069ff0f7a2c41046325ef2

問題を見て最小費用流に帰着するの、何を考えれば良いのか…

AC

グラフの構築

添え字を間違えるミス

負の辺があるとたまに正しくない値を返すのでINFを足しておく

code:python

def solve(N, M, AS, BS, RS):

INF = 10 ** 5

mcf = MinCostFlow(N + 5)

start = N

goal = N + 1

round = N + 2

for i in range(3):

mcf.add_edge(start, round + i, M, 0)

for i in range(3):

for j in range(N):

mcf.add_edge(round + i, j, 1, INF - r)

for j in range(N):

cs.append(0)

for k in range(3):

mcf.add_edge(j, goal, 1, c)