Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1202-8dfb248d
この記事にトラックバックする(FC2ブログユーザー)

PKU 3762 - The Bonus Salary! (この記事を編集する[管理者用])

Source

PKU Campus 2010 (POJ Monthly Contest 2010.05.09) (参加記録)
PKU 3762

問題概要

N個以下のタスクが与えられる.
タスクiを行うには[A_i,B_i)の間,タスクに取り組まなくてはいけなくて,タスクをこなすとC_iだけ利益がある.
1人が同時にできるタスクは1個のみで,K人だけ人がいる.
利益の最大値を求める問題.
Nは2000以下,Kは100以下.

解法

最小費用流.
各タスクの,開始,終了をノードにして,2N個のノードを作る.
時間が自分より後のもの(か等しいもの)に流量無限大,コスト0の枝を張る.
各タスクの,開始から終了に向けて,流量1,コスト -C_i の枝を張る.
このようなグラフを考えれば良いが,このままだとTLEだった.
終了に対応するノードを端折って,終了のかわりに次の開始のノードを使う.
開始時間でソートしておいて,次のノードに向けてのみ,流量無限大,コスト0の枝を張ることにする.
こうすることで,ノード数N,枝数O(N)にできて,これでギリギリ通った.
また,流量無限大の枝のコストを10000にして,コスト -C_i の枝は,タスクiからタスクjに枝を張っているならコスト 10000*(j-i)-C_i に変更したら速くなった.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1202-8dfb248d
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。