スポンサーサイト

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

Codeforces Round #165 (Div. 1) C : Flawed Flow

頂点数 n、辺数 m の無向グラフにあるフローを流したものが与えられる。
ただし、フローの向きは分からない。

正しいフローになるようにすべての辺の向きを定めよ。
得られる有向グラフは閉路を含んではいけない。
また、ソースに入ってくる辺があってはいけない。

・ 2 ≦ n ≦ 2・10^5
・ n-1 ≦ m ≦ 2・10^5
・ 頂点 1 がソース、頂点 n がシンク
・ 題意を満たす解の存在は保証されている

解答

まったく検討がつかなかったので editorial を見た。

まず、ソースとつながっている辺の向きは制約からすぐにわかる。
すると、ソースと隣接する頂点のうちの少なくとも一つは、「その頂点とつながっているまだ方向が定まっていない辺は、すべて出ていく辺である」という性質を満たす。
なぜなら、もしそうでないとすると、それはグラフをトポロジカルソートできないということで、つまりグラフが閉路をもつことになり制約に反する。
太字の性質をみたす頂点は、流入量と流出量が等しいという関係を使って特定することができる。
それ以降も、同じように太字をみたす頂点を一つずつ確定していくことができる。

シンクだけは例外 ( 流入量 = 流出量という条件がないので同じロジックが使えないから? ) なので注意する。

実装は単に BFS すればよいので、計算量は O(n + m) になる。

すごい。

ソースコード

http://codeforces.com/contest/269/submission/3067368
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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