TTPC2015L

https://gyazo.com/fdaa6debdfe439cb7fd207ada2b49c45

考えたこと

最小カット関連問題であることは既知だが、テーマが最小カット=最大流なだけか、解法も最小カットなのか不明

青の辺を全部取り除いた時の最大流は、単なる定数なのでまず求めてしまえばよい、以下で定数Fとする

与えられたグラフの青の辺に対して「消す消さない」の二択をやって、最大流をFにする問題

青の辺は200あるので2^200は無理だから最小カットで解くのが良さそう？

「最大流がF」という制約をどうやって表現するのか？

青の辺を全部取り除いた状態での最大流の塗り分けから「最大流を増やさない」という条件で辺を足していったものが答えだろうか？

そうともいえない気がするが一旦それで考えてみよう

https://gyazo.com/6bab8fe1daa758f42c2371e691b03d0a

辺Dは、選択するとSとTが繋がってしまうので最大流が増える

1のコストを払って切るべき

2つの無限大辺は冗長な書き方で、どちらかを縮めても問題ないが、後でやる

辺Cは、選択するとSとAがつながる

でもAはSになっても問題ないので切る必要がない

辺をE,Fと繋がってるものも同様に表現できる

この場合はどちらかを切るべき

無意識に「切る」メタファーで考えたせいで無駄な設計になってしまった、やり直し

左グラフで辺を残すか残さないかの選択が、右グラフでは頂点を赤で塗るかどうかに対応する

辺を消す時、コストを1支払う

https://gyazo.com/40d6397ff6a11ab738e5996b87257dfd

これでいいんだろうか？

他の人の解説