2016-07-10から1日間の記事一覧

最小流量制限付き最大流

SRMで最小流量制限付き最大流が出ました。(SRM694Div1 Hard) とりあえず自分がやった方法をメモしておきます。まず、下図のようなグラフのs→tの最大流が求めたいとする。 以下のように変換する。(蟻本に載ってる図と同様) 超頂点S,Tを作り、u→vにL以上R…