https://colopl2018-final.contest.atcoder.jp/tasks/colopl2018_final_e
rep(i, H + 1) rep(W, M) AS[i] += min(i, A[j]);
通した人の多くがこのようなコードを書いているわけですが、これだけ解説します。
Bがsource側、Aがsink側だとします。
Bのうちi辺がcutされたとして、この時のmincutを求めましょう。
すると容量Aiの辺をsupersourceのグループに含めるとcostはAi,逆に含めないとcostはiになります。supersourceのグループ→supersinkのグループに向きが付いている辺のコストを求めるとこうなります。なので
mincut = Σ(k< i)Bk+Σ(0<=l< W)min(Ai, i)となります。このΣ(0<=l< W)min(Ai,i)を求めているのが上のコードです。
editorialを素直にコードにしたような人が少なかったので結構理解に苦戦しました。
なんか変な貪欲でみんな通しているのかなぁと思いましたが、結局フローをベースに考えているようですね。
あとHallの結婚定理は辺に重みが付いている時は使えないので注意しましょう。
