考えたこと
- 最小カット関連問題であることは既知だが、テーマが最小カット=最大流なだけか、解法も最小カットなのか不明
- 青の辺を全部取り除いた時の最大流は、単なる定数なのでまず求めてしまえばよい、以下で定数Fとする
- 与えられたグラフの青の辺に対して「消す消さない」の二択をやって、最大流をFにする問題
- 青の辺は200あるので2^200は無理だから最小カットで解くのが良さそう？
- 「最大流がF」という制約をどうやって表現するのか？
- 青の辺を全部取り除いた状態での最大流の塗り分けから「最大流を増やさない」という条件で辺を足していったものが答えだろうか？
- そうともいえない気がするが一旦それで考えてみよう
- 辺Dは、選択するとSとTが繋がってしまうので最大流が増える
- 1のコストを払って切るべき
- 2つの無限大辺は冗長な書き方で、どちらかを縮めても問題ないが、後でやる
- 辺Cは、選択するとSとAがつながる
- でもAはSになっても問題ないので切る必要がない
- 辺をE,Fと繋がってるものも同様に表現できる
- この場合はどちらかを切るべき
- 辺Dは、選択するとSとTが繋がってしまうので最大流が増える
- 無意識に「切る」メタファーで考えたせいで無駄な設計になってしまった、やり直し
- 左グラフで辺を残すか残さないかの選択が、右グラフでは頂点を赤で塗るかどうかに対応する
- 辺を消す時、コストを1支払う
- あ、これ辺を頂点にして二部グラフだな
- これでいいんだろうか？
- 他の人の解説
