読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #347 (Div. 1) C. Graph Coloring

http://codeforces.com/problemset/problem/662/B

問題概要

辺に R or G の色を持つ無向グラフが与えられる。ひとつ頂点を選んで、その頂点に接続している辺の色を反転する操作を繰り返しおこない辺の色を統一したい。

操作回数が最小になる方法をひとつ示せ。

解法

R に揃える場合と B に揃える場合をそれぞれ解いてみて、小さい方を採用する。R に揃えることを考えてみよう。

それぞれの頂点を 2 回以上反転するのは無意味なので、0 回か 1 回の反転だけを考えればいい。反転する頂点を黒で塗ることにすると、辺の両端の色はそれぞれ次のようになる。

f:id:pekempey:20160417110854p:plain:w400

したがって一つ頂点の色を決めると連鎖的に他の頂点の色も決まる。

f:id:pekempey:20160417111409p:plain:w400

白と黒の役割を入れ替えても条件を満たすので、反転する回数が少なくなる方の色を使えばいい。

今回はグラフが連結とは限らないので、各連結成分に対してこの作業を繰り返す必要がある。

Codeforces Round #347 (Div. 1) C. Graph Coloring

連結性を勝手に仮定してしまい 1WA。Union-Find を使って 2-SAT を解く方法もある。