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++
原理は二部マッチングに近い。
最小費用流は速いと聞くが、どのくらいが限界なのかがよく分からない。