Spent Fuel Disposal

解説等が一切見当たらなかったので、殴り書きをする

jag 夏合宿 2019 day2 の問題で、たしか作問担当は筑波大だったと思う
論文（多分これ？）を読むと解けますと言われたことしか覚えてない

解法は、 $S,U$ を source, $T,V$ を sink としたグラフと $S,V$ を source, $T,U$ を sink としたグラフでの最大流の min
これがなんとなく正しいかもと言う気持ちになるための説明を書く

二つのグラフのフローは簡略化するとそれぞれ以下のように描ける

両方のグラフに登場する $S,T$ パスと $U,V$ パスについては元の問題で求めたいパスに含まれる*1
一方で、左のグラフの $S,V$ パスと $U,T$ パス、右のグラフの $S,U$ パスと $V,T$ パスについては、以下のようにして $S,T$ パスと $U,V$ パスに変形が出来る

従って、この解法が正しそうな気持ちになる

実際には二つのグラフで得られる最大流で $S,T$ パスと $U,V$ パスがそれぞれ一致しているとは限らないためもう少し議論が必要だと思います

*1:無向グラフなのでパスの向きは気にしなくて良い

blogskol