スポンサーサイト

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

VK Cup 2012 Round 3

2012/04/09
VK Cup 2012 Round 3

Tags : プログラミング Codeforces 未解決

問題

問題セットの原文はここを参照。

A. Variable, or There and Back Again

頂点数 n, 辺数 m の有向グラフがあり、各頂点には 0, 1, 2 のいずれかのラベルがついている。
有向グラフ上のパスで、
・ 始点のラベルが 1
・ 終点のラベルが 2
・ 始点以外にラベル 1 の頂点を含まない
をみたすものを考える。
すべての頂点に対して、その頂点を含む、上記のパスが存在するかどうかを判定せよ。

1 ≦ n, m ≦ 10^5

C. Machine Programming

n 個のタスクを k 台のコンピュータで並列処理する。
仕事 i は一台のコンピュータを時刻 s[i] から s[i]+t[i]-1 まで拘束し、利益 c[i] をもたらす。
一台のコンピュータは同時に一つまでのタスクしか処理できない。
処理したタスクの利益の和を最大化し、そのときのタスクの割り当て方を一つ求めよ。

1 ≦ n ≦ 1000
1 ≦ k ≦ 50
1 ≦ s[i], t[i] ≦ 10^9
1 ≦ c[i] ≦ 10^6

解答

A.
与えられるグラフに対してすべてのラベル 1 から BFS する。
さらに、逆グラフに対してすべてのラベル 2 から BFS する。
両方から到達可能な頂点が、すなわち題意のパスに含まれる頂点である。
ただ、パスの途中にラベル 2 を含んでいいとか、微妙な非対称性があって、ちょっとややこしい。
http://www.codeforces.com/contest/164/submission/1499548

C.
「あ、これ蟻本でやった問題だ!」
蟻本の最小費用流のページにほぼ同じ問題が載っている。

ただ、なんでこれでいいかを理解していなかったので、開区間を閉区間に変えたり、選んだ集合を復元する部分にかなり手間取った。
蟻本と同じように、あらかじめグラフを変形して負辺を消す方法でやったけど、これだと n+k 単位くらいフローを流さないといけなくて遅い。n 単位が流れる道は最初からわかっているので、そこだけ別途流す手はあるけど、最小費用流のコードに手を加えないといけなくて大変。
それよりは、負辺のあるグラフをそのまま扱うことにして、最初の一回だけ Bellman-Ford でポテンシャルを求めてやる方が楽でよかった。
http://www.codeforces.com/contest/164/submission/1502615
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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