問題
H個の木がある。各木のはじめの高さはで与えられ、
の高さだけ毎日成長する。木を切るためのデバイスがD個与えられる。これは、高さが
以上の木を高さ
に切ることができる。その日の最後にデバイスを使用することができる。各デバイスは1日に一度しか使えず、各木は1日に一度しか切れない。以上の操作を行ったときのT日目の木の高さの総和の最小値を求めよ。
解法
最小費用流を用いる。以下のようにエッジを張る。ノードには木、デバイス、日とsource、sink、noneがある。noneはデバイスを全く使用しないための頂点である。
- sourceと各木を、容量1、コスト0で結ぶ
- 各木とnoneを、容量1、コスト
で結ぶ。
- noneとsinkを、容量H、コスト0で結ぶ。
- 各木と各日を、容量1、コスト(T-k)で結ぶ。kはデバイスを使用する
日を示す。
- 各日と各デバイスを、容量1、コスト
で結ぶ。
- 各デバイスとsinkを容量T、コスト0で結ぶ。
この処理では、木の高さが以下でもデバイスを使用してしまっている。しかし、求めたいの木の総和の最小値であるため、この時が最小値となることはないため、正しく答えを計算できる。
計算量
N: max(H, D, T)
H: 木の数
D: デバイスの数
T: time