【今日の精進】ABC247G - Dream Team

毎日格上の問題を倒すやつの23日目です。

問題リンク

atcoder.jp

問題概要

「所属大学も得意分野も異なる 人の強さの合計の最大値」をありえるすべての に対して求めてね。¹

解法

いわゆる重み付き二部マッチングです。

コストを負にして最小費用流をしたい気持ちになりますが、めんどくさいことになるので全部にでっかめの数を足しておきます。

…と、言葉の上では終わりですがACLでは関数の仕様がめんどくさいので注意して実装しなければなりません。

提出コード

from atcoder.mincostflow import MCFGraph

INF=10**9+7
N=int(input())
gr=MCFGraph(302)
for i in range(N):
    A,B,C=map(int,input().split())
    gr.add_edge(A-1,150+B-1,1,INF-C)
for i in range(150):
    gr.add_edge(300,i,1,0)
    gr.add_edge(i+150,301,1,0)
ans=gr.slope(300,301)
ans.append((INF,INF*INF))
print(ans[-2][0])
pos=0
for i in range(ans[-2][0]):
    if ans[pos+1][0]==i+1:
        pos+=1
    print(INF*(i+1)-ans[pos][1]-(ans[pos+1][1]-ans[pos][1])*(i+1-ans[pos][0])//(ans[pos+1][0]-ans[pos][0]))

Submission #46482971 - AtCoder Beginner Contest 247

感想

やっぱフローはわかると楽しいね

---

1. ここも雑になったら終わりだよ↩