最近フロー関連をやってたのでそのメモ 最大流 頂点辺の有向グラフ 各辺には容量が定義されている をそれぞれ頂点から出る/入る辺の集合とする 始点を，終点をとする LPの形で書くと以下の通り ford-fulkerson 最大流を求めるアルゴリズムの一つ 最大流の流…

燃やす埋める問題は以下の問題である 頂点を赤と青に塗り分ける 塗り方の依存関係によってスコアが変動する (例) 頂点 が赤で頂点 が青に割り当てられたとき 失う スコアの和の最小化を行え この問題は最小カットに帰着して解くことができる 必ず赤が割り当…