SRM642Div1Medium
問題
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