問題リンク
問題概要
N頂点M辺の無向グラフが与えられる。各頂点を白または黒に塗り分け、更に辺に重みを割り当てる方法であって次の条件を満たすものは存在するか。存在すれば1つ構築せよ。
- \(1\leqq i\leqq N\)にし、点iから色の異なる点に移動するための最小コストは\(D_i\)である
解法
まず、各辺の重みをinfとしておく。
後から辺の重みが大きい物を足していっても、それより小さい最小コストが既に実現している点には影響しないので、Dが小さい点から決めていくのが良いとわかる。
Dが小さい順に、次のアルゴリズムで点iの色と辺の重みを決める。
- 点iと直接辺で繋がっていて既に色が決定している点があれば、それと異なる色に塗って、辺の長さを\(D_i\)とする。
- もし色が決定している点が無ければ、直接辺で繋がっている点のうち最もDが小さい点jを取る。点の取り方から\(D_i \leqq D_j\)が成り立つ。\(D_i = D_j\)ならば辺の重みを\(D_i\)にして点iを白、点jを黒に塗る。\(D_i < D_j\)ならば条件を満たすことは不可能なので-1を出力する。
最後まで重みを決めなかった辺はinfでいい。
提出
https://atcoder.jp/contests/keyence2020/submissions/9581586
感想
時間ギリギリで解けたので嬉しい。
