久々にまともな記事(まともではない)
正当性がいい感じに示せた気がするのでメモ
T を +EPSする写像とする(ガバガバ定義)
MST(G) = floor(MST(T(G))) を示したい
MST(G) <= MST(T(G)) は明らか(+EPS してコストが減ったら、やばいだろ)
また、MSTの定義から、MST(T(G)) <= T(MST(G))
両辺を適当にfloorして、終わり!
久々にまともな記事(まともではない)
正当性がいい感じに示せた気がするのでメモ
T を +EPSする写像とする(ガバガバ定義)
MST(G) = floor(MST(T(G))) を示したい
MST(G) <= MST(T(G)) は明らか(+EPS してコストが減ったら、やばいだろ)
また、MSTの定義から、MST(T(G)) <= T(MST(G))
両辺を適当にfloorして、終わり!