beet's soil

競プロのことなど

+EPSしてdistinctにするテク

久々にまともな記事(まともではない)

正当性がいい感じに示せた気がするのでメモ

T を +EPSする写像とする(ガバガバ定義)

MST(G) = floor(MST(T(G))) を示したい

MST(G) <= MST(T(G)) は明らか(+EPS してコストが減ったら、やばいだろ)

また、MSTの定義から、MST(T(G)) <= T(MST(G))

両辺を適当にfloorして、終わり!