AOJ 1519 - Room of Time and Spirit
Room of Time and Spirit | Aizu Online Judge
提出コード
初めて重み付きUnion-Find木を使いました。
参考にしたブログはこちらになります。
ただ、この問題はライブラリを貼るだけだと対応できないので、少し考察をする必要があります。
SRLU室に"IN"したとき、INした二人ともCだけ戦闘力が上がるからです。
INしたノードの重みにCを足しても矛盾が生じないようにうまく整理してあげる必要があります。
解決方法としては、INした二人を表すノードの、子ノードの重みをCずつ減らしていけばよいです。
あるノードに対しての子ノードを調べるには、それぞれのノードに対し、子になるように繋いだノードのリストを持たせてあげて、それが未だ子になっていることを調べてあげればよいです(経路圧縮の関係でもう子になっていない可能性もあるので、毎回調べないといけません)。ということで、今INしているノードの番号と、リストにいるノードの根の番号が一致したら、リスト側のノードの重みをC減らしてあげます。
また、根の重みは0になるようにうまく調整してあげる必要がありますが、根ノードの根は自分自身なので、自分自身も子になっているかどうか調べるリストにいれてあげると、上手く処理ができスッキリします。
