nanikaka https://blog.hatena.ne.jp/nanikaka/ nanikakaのAOJ航海日誌 https://nanikaka.hatenadiary.org/ AOJ Volume20 問題リンク Rock Man 概要 N種類のアイテムを全て作りたい。アイテム i を作るにはそれぞれ、day1_iの日数がかかる。アイテム i を作るとき、ある別のアイテムを既に作っていると作業が効率的になるのでday2_iで済むようになる。 全てのアイテムを作るのにかかる最小の日数を求めよ。 N 0 解法 アイテムを頂点とし、i→jの辺を、アイテム i を作っているとアイテム j がday2の日数で作れるという関係を表すものとします。すると、どの頂点も入次数1以下、出次数0以上のグラフが出来上がります(ただし、自己ループ辺は除きます)。 day2 強連結成分分解してDAGの形にします。DAG… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnanikaka.hatenadiary.org%2Fentry%2F20111210%2F1323483017" title="AOJ2033 Rock Man - nanikakaのAOJ航海日誌" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-12-10 11:10:17 rich https://nanikaka.hatenadiary.org/entry/20111210/1323483017 1.0 100%