maxflow 個人的備忘録
色々読んで適当に掴んだ雰囲気をなぐり書きしていくので表現の厳密さ，丁寧さには欠けると思います 読み込んだのをそのまま吐き出す感じだったりするのであらゆる記事の丸パクリっぽくなるかもしれないし，独自の解釈が混ざっているので信憑性に欠ける部分も多いかも，あと読みやすさも全く考慮していません（ごめんなさい）
maxflowとは
maxflowはあるグラフを考えたときに，そのうちの２頂点s→tにできるだけ大量に水を流すとmaxどれくらい流れますかという問題です（それはそう）
双対問題について（最小カット）
では，上記の問題で「tに水が流れないような辺の取り除き方を考えた時の，取り除いた辺の容量の総和を最小化せよ」という問題を考えてみます．まず，最大流量をFとするとFまでは流せちゃうわけですから，F未満であれば絶対に水を流せてしまうのは明らかです．
最大流量が流れる時の辺の状態に思いを馳せてみると，任意の辺(u→v）に流れる流量fはその辺の容量をcとして，
f=min(c,(uに入ってくる流量)-(uから出る他の辺に流れていく流量))
であると表せます．ここでuから直接到達できる頂点の集合Vを考えると，
(V全体に入ってくる流量の総和)<=(uに入ってくる流量)
であるはずです．ここで，始点sには無限の水が注がれているものと考えてください．すると，u→（V内の各頂点）へ流れるときにもし辺の容量が十分大きかったら，流量は減らないはずです．つまり元々のmaxflowを「なんで高々それだけしか流せないんだ」という問題であると考えると，実際に流したかった流量に対して辺の流量が小さい，すなわちf==cとなるような辺が本質であるような気がしてきます．そのような辺集合をEとすると，Eの部分集合に辺の容量の総和がFとなるような集合E'が存在します．それは当たり前で，元々始点には無限の水を注いでたのに，その制約のせいでFしか流せなかったとみなせるからです．
さらにE'の各辺はすでに辺の容量ギリギリまで流れていることを考えると，それらの容量をさらに小さくしていけばどんどんtへの流量が少なくなっていってやがて0に収束していくことがわかります．つまりE'が元の問題を満たす集合であると言えて，また，求める総和はFであるということがわかります．
この問題を最小カットと呼び，maxflowの双対問題（＝同じ解き方で求めることができる）として有名です．
ここでのポイントはある条件Lを考えたときに「Lを満たすようにある量を最大化する」という問題だったのが，「Lを満たさなくするようにコストを最小化する」という問題に帰着できるということです．最大化する問題だったはずなのに最小値を求めるのと等価であると言う事実は凄く気持ち悪いですが，最大流量はあくまで下界を与えるものだと思うとすっと入ってきやすい気がします．
結局何
さっきの文章である条件Lを言及しましたがもう少し具体的に言えば，Lは「複雑な制約が絡んでいるうちで（これはグラフ全体に対応します），P（頂点sに対応）ならばQ（頂点tに対応）である」といえて，またLを満たさないとは「複雑な制約が絡んでいるうちで，PならばQでない」であると言えます．後者の方に注目してみると，「PならばQでない」は，対偶を取ることにより「QならばPでない」と同値です．つまりこのことからP,Qは独立であるようにするということが言えます．よって
「独立な操作P,Qが存在して，各制約について，操作Pを行ったときにコストX，操作Qを行ったときにコストYかかる．どっちかに割り振れ」
という条件に帰着できるわけです．maxflowを使えばこんな形の問題を解くことができます．
チートシート
ACLを前提に考えます．
#include<atcoder/maxflow>
atcoder::mf_graph<ll> g(n+2);
が宣言されているものだと思ってください．nは制約の個数（というとやや語弊があるが）に対応します．また，頂点S,Tを操作P,Qに対応させるとします．
・最終的に求める答え
g.flow(S,T);
・制約Cは「操作Pを割り当てるときにコストがXかかり，操作Qを割り当てるときにコストがYかかる」
g.add_edge(S,C,Y);//S→Cが成り立たないときを考えるので，コストが逆になることに注意
g.add_edge(C,T,X);
・制約Cに操作Qを割り当て，制約Dに操作Pを割り当てたときにコストがZかかる
g.add_edge(D,C,Z);
・制約Cにも制約Dにも操作Pを割り当てたときに報酬がGもらえる（コストだとNP-Hardになる）
この制約自体を新しい制約Eとおく．
//あらかじめGだけもらっておく
ans-=G;
//Eが操作Qに割り当てられている場合はGだけ支払う（元の加算分を考えるとチャラ）
g.add_edge(S,E,G);
//EはPに割り当てられているが，CがQに割り当てられている場合はINFだけ支払う（EがPなら，CとDもPであるようにしたいので，Qにいかないようにする）
g.add_edge(E,C,INF);
//Dも同様
g.add_edge(E,D,INF);
・制約C,D,Eが全てPに割り当てられたときに報酬Gもらえる
この制約自体をFとおくと
ans-=G;
g.add_edge(S,F,G);
g.add_edge(F,C,INF);
g.add_edge(F,D,INF);
g.add_edge(F,E,INF);
以下は非常に参考にした文献です ありがとうございます
蟻本p188-p193
