＜mcf_graph(MinCostFlow)＞
最小費用流
sからtに流量を流せるだけ流したときのコストの最小値を求める
流量にlimを定めることも出来る
■O - 輪投げ（第三回 アルゴリズム実技検定 過去問）
求めたいもの：最終得点の最大値
反転させ最小値を求めることでMinCostFlowが使えるようになる。
以下のように頂点を作る
始点:s
ラウンド:r1,r2,r3
棒:b1,b2,b3,,,,,,bn
終点:t
以下のように張る(cap,cost)
s->ri (m,0)
ri->bj (1,INF-Pij)
bj->t (1,AiBi),(1,AiBi^2-AiBi),(1,AiBi^3-AiBi^2)
上記のようにした時の3*INF*M-ansが答え
※
負のcostは流せないのでINFを足しておく(3*M本流れる)
AiBi < AiBi^2-AiBi < AiBi^3-AiBi^2
となるお陰で上手くいく
■M - 分割（第七回 アルゴリズム実技検定 過去問）
求めたいもの：合計スコアの最小値
以下のように頂点を作る
始点:s
頂点:a1,a2,a3......an
頂点:b1,b2,b3....bn
終点:t
以下のように張る(cap,cost)
s->a (1,0)
a->t (1,c)
b->t (1,0)
ai->bj (1,abs(a[a[i]]-a[b[j]]))
■K - ニワトリのお見合い（第八回 アルゴリズム実技検定 過去問）
求めたいもの：達成可能な最大値
最大値なので、反転させて最小値を求めることでMinCostFlowが使えるようになる。
以下のように頂点を作る
始点:s
頂点:P1,P2,P3......Pp
頂点:Q1,Q2,Q3....Qq
終点:t
以下のように張る(cap,cost)
s->p (1,0)
q->t (1,0)
pi->qj (1,INF-(a[i] - b[i] + c[j] - d[j]))
ここまでと同じようにflow()で答えを求めたいが
INFの補正を無視した流量ごとの最適解がわからない。
が、aclにはslope()というものが提供されているので求まる
■ABC247G - Dream Team(黄:2159)
求めたいもの：ちょうど i 人で構成されるチームに所属する人の強さの合計の最大値
最大値なので、反転させて最小値を求めることでMinCostFlowが使えるようになる。
以下のように頂点を作る
始点:s
頂点:a(各大学)
頂点:b(各得分野)
終点:t
以下のように張る(cap,cost)
s->a (1,0)
b->t (1,0)
ai->bj (1,INF-data[i][j])
上と同じようにslope()で解けるが
slopeの戻り値には罠があって折れ線の頂点が帰ってくるので戻りをそのまま使う訳にはいかない。
◆Another
214H,224H,231H
＜mf_graph(最大フロー)＞
最大フロー：始点から終点にどれだけの流量を流せるか
■ABC205F(黄:2088)
求めたいもの：駒を置ける数の最大数
以下のように頂点を作る
始点:s
終点:t
行:h
列:w
マスIN:d0(ij)
マスOUT:d1(ij)
以下のように張る
s->hi
wi->t
h->d0
d1->w
d0->d1
d0,d1の存在は各マスに１つしか置けないという状態を表現している
最大流量が答えになる
■ABC241G - Round Robin橙:2422)
求めたいもの：辺を張ったときにフローがn*(n-1)/2本流せるか
以下のように頂点を作る
始点:s
終点:t
選手:pi
試合:gij
以下のように張る
s->gij
gij->pi,pj(勝敗が確定していない時)
pi->t(capは優勝者なら優勝者の勝ち数、非優勝者なら優勝者の勝ち数-1)
■ABC263G - Erasing Prime Pairs(黄:2261)
これは最大フロー一回で解けるが非本質なので略
■ABC274G - Security Camera 3(黄:2340)
頂点(i,j)に対してxij,yijが定められる
すべての頂点に対してxij,yijのいずれかが選択されている必要がある。
xij,yijの選択数の合計を最小にしたい
以下のように頂点を作る
始点:s
終点:t
頂点:x
頂点:y
以下のように張る
xを選ぶ:=xをTに
yを選ぶ:=yをSに
xijとyijのいずれかを選ぶ:=xij,yijの間にINFを張る
ｔ
＜mf_graph(最小カット)＞
最小カット：集合とs(始点)とt(終点)に分けるs->tとなっている辺のcapの合計を最小にする
■N - 壁の建設計画（第11回 アルゴリズム実技検定 過去問）
求めたいもの：頂点をs,ｔに振り分けた時の最小カット
以下のように頂点を作る
頂点:d0(ij)(各頂点のOUT)
頂点:d1(ij)(各頂点のIN)
始点:上のd0(0,0)
終点:上のd1(n-1,n-1)
以下のように張る(cap)
d1(i,j)->d0(k,l)(INF)隣接四方向
d0(i,j)->d1(i,j)(c[i][j])
壁を立てるのはd0(i,j)->d1(i,j)を切断する(s,tに属させる)のと同じことなので
flow()を実行した後にどの頂点がs,tに属するかはmin_cut()で取得できる
■ABC193F - Zebraness(橙:2475)
求めたいもの：頂点をs,ｔに振り分けた時の最小カット
ただしこの問題設定では解けないので、グラフの一部(0!=(i+j)%2)を反転させ
色が異なる組数の最大値
⇒色が同じ組数の最大値
⇔色が異なる組数の最小値
と読み替える必要がある
以下のように頂点を作る
始点:S(白)
終点:T(黒)
マス目:n^2個
以下のように張る
すでにSかTかが決まっているもの('?'!=s[i][j])はcapがINFの辺でSかTに結ぶ。
隣接する頂点にcap1の辺を貼る
■ABC225GG - X(橙:2566)
求めたいもの：バツを付けた箇所-バツをつけるのに使った線分のコストの合計の最大値を求めてください
⇔バツを付けない箇所+バツをつけるのに使った線分のコストの合計の最小値
Sに属する=バツをつける
Tに属する=バツをつけない
とし
線分のコストを線分の右下、左下すると最小費用龍の形になる
■ABC239G - Builder Takahashi (黄:2215)
上記のN - 壁の建設計画（第11回 アルゴリズム実技検定 過去問）とほぼ同じ
解説略
■ABC259G - Grid Card Game (橙:2428)
求めるもの：得点の最大値
⇔選択することによって失う特典の最小値
以下のように考える
行を選択するとSに含まれる
選択しないとΣa[i][j]失う
⇔s->iにcapΣaを張る
列を選択するとTに含まれる
選択しないとΣa[i][j]失う
⇔i->tにcapΣaを張る
a[i][j]<0のとき、iをSにjをTに含ませたくないのでcapINFを張る
a[i][j]>=0のときダブルカウントされるのでcapa[i][j]を張る
負辺除去はいつも通り
◆Another
227H,237H
