SRM642 Div1 Medium TaroCutting - yoshiokatsuneoのブログ

[問題]

N本の木とD本のカッターがある。木は最初height[i]で1日にadd[i]のびていく。カッターは木の高さをdevice[i]丁度にすることができる。

各カッターは、1日に一回だけ使うことができる。

time日後、最小の木の高さの合計はどれぐらいか?

[解答](C++, 後で)

それぞれの木については、高々１回切ればいいので、木の高さの合計をコスト、流量(切った数と切らない木の合計)Nの最小費用流で計算する。

カッターはそれぞれの日に一度だけ使えるので、STARTからD * time個の頂点にコスト0、流量1の辺を張る。そこから、N本の木に対応する頂点まで更にコストdevice[i]+(time-i-1)*add[i]、流量1の辺をはる。カッターを使わない場合のため、STARTからN本の木までコストheight[i]+time*add[i]、流量1の辺も張る。木からSINKまでコスト0、流量1の辺を張る。

さらに、計算量を減らすため、カッターをdeviceでソートし、カッターiからカッターi+1にコスト(device[i]-device[i+1])(負の数だけど先の頂点はそれより大きい辺しかこないのでDijkstraでもOK)、流量Dの辺をはり、カッターから木の辺はそのカッターでしか切れない範囲までの辺にする。

[コード]

[感想]

テストケースによっては計算時間が1.9秒程度なので、ぎりぎり。。。