スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #167 (Div. 1) C : Dima and Horses

頂点数 n、辺数 m の無向グラフが与えられる。
グラフの頂点に白色か黒色かを塗り、すべての頂点 v に対して、条件
(*) v と隣接する頂点で v と同じ色のものは高々一つしかない
が満たされるようにしたい。

具体的な塗り方を一つ求めよ。そのような塗り方が存在しないならそれを指摘せよ。

・ 1 ≦ n ≦ 3・10^5
・ 0 ≦ m ≦ 3・10^5
・ グラフは単純
・ グラフのどの頂点も次数は 3 以下

解答

Editorial を読んだ。

z = Σv ∈ V ( v と隣接する頂点で v と同色のものの個数 )
という量を考える。

条件 (*) をみたしてない頂点 v を一つ好きに選び、v の色を塗り替えると、z の値は真に減少する。
このことは、次数が 3 以下という制約に注目すれば簡単に示せる。

なので、このような逐次改善をくり返していけば、z の値は減少してゆき、やがて ( z == 0 となったタイミングで ) 正しい塗り方が求まる。

z ≦ 6n とかなので、BFS っぽく適切に実装すれば O(n) で解ける。
自分のコードは、そこをさぼって雑にループしているので最悪計算量はよくわからないけどきっと速い。

こういうポテンシャルみたいなのを考える問題はなかなか自力で解けない。もっと数をこなしたい。

ソースコード

http://www.codeforces.com/contest/273/submission/3129947
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。