UVa 11544 Recruiter's Problem

二部マッチングの練習をしようと思ったら丸一日かかった…

グラフはこんな感じ。

SRC --1-- CANDIDATE(i) --1-- PROJECT(j) --r-- SINK

まず最初にここと同じで、一人目の一つ目の仕事からgreedyに割り振り、流量が減らないなら採用する事を繰り返す、という方針でやる。手元だと正しい答えが出ているように思えるが残念ながらTLE。定数倍の最適化を繰り返して何とか２倍くらい速くなったり、dinicを止めてford-fulkersonにしたらさらに２倍くらい速くなったりしたがTLEは変わらず。少し考えると

1
5 5
1 1 1 1 1
5 1 2 3 4 5
4 1 2 3 4
3 1 2 3
2 1 2
1 1

のようなケースの時にN^2回（最悪50^2=2500回！）（追記：正しくはN*(N+1)/2回ですね）の最大流が回るのでTLEなのも分からなくもない。どうしたもんかな〜〜〜〜と思ってforumを覗くとbinary-search出来るんじゃん？とある。うぉ！これだと最大流がNlogN回になって最悪ケースでも350回程度に押さえられる。素晴らしい〜（逆に50回で済むのが350回になって7倍程度遅くなるケースもあるけども）。と思って実装に取りかかるも、言うは易しで、どうやんだこれ？状態になり、全員使えるケースでは上手く行くが余るケースで上手く行かなかったり、そもそも「ある人が、自分の希望する仕事のうちx番目がらy番目の候補のどれかに必ず割り振られるような状態で最大流を求める」とかややこしすぎるだろ〜どうすんだ〜ってなったり、binary-searchなんて出来るのかと疑ったりしたけども最終的に上手くいってACもらった。嬉しす。

しかしdinicよりford-fulkersonが２倍速かったりまさかのbinary-searchで通ったりグラフを操作して「ある条件を満たすフロー」を流す事を勉強したり色々と良かった。