RUPC 2016 day3 E: Arai's

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=E

解法

x 組作るのに必要な噂の回数が最小費用流で求まることを使えば、噂の回数が K 以下になるような組の数を二分探索できる。

x 組作るのに必要な噂の最小回数は次のようなグラフに x だけ流すと求まる。

  • 容量はすべて 1
  • A→B がよく思ってないなら cost++
  • B→A がよく思ってないなら cost++

原理は二部マッチングに近い。

f:id:pekempey:20160309135101p:plain:w450

RUPC 2016 day3 E: Arai's

最小費用流は速いと聞くが、どのくらいが限界なのかがよく分からない。