Rent a Car (UVa 12437 World Finals Warmup 2012 1)
問題
C種類のpi円の車がci個ある。一度使った車はサービスセンターで修理をしないと以降使うことはできない。修理の種類はR個あって、それぞれsi円・di日で修理が完了する。これからN日間の車の必要台数riが与えられるので、どの車を買い、どのように修理を行うかをスケジュールして必要なコストを最小化せよ。
1<=N,C,R<=50
1<=ri,ci,pi,di,si<=100
解法
最小費用流で解く。グラフは
- SOURCE,DEST
- MSOURCE,MDEST
- IN頂点*N
- OUT頂点*N
の2N+4個の頂点から構成される。また車の全必要台数-車の全台数をneedとする。
まずx番目のIN頂点からx+di+1番目のOUT頂点へ容量∞、コストsiの辺を張る。またx番目のOUT頂点からx+1番目のOUT頂点へ容量∞、コスト0の辺を張る。これらの辺の意味はINの日に車を使ったらOUTの日に車が戻ってくることを表す。
次にMSOURCEからx番目のIN頂点、x番目のOUT頂点からMDESTへ容量ri、コスト0の辺を張る。この辺はx日目に使用する(使いまわせる)車の台数は多くてもri個という制約を意味する。
次にSOURCEからMSOURCE、MDESTからDESTへ容量がneed、コスト0の辺を張る。もしneedが負の場合はMSOURCEからMDESTへ容量が-need、コスト0の辺を張る。これは最低need台、車を使いまわさなければならないとう制約を意味する。
最後にMDESTからMSOURCEへ容量がci、コストが-piの辺を張る。これは車を使い回して節約できるコストを意味する。
車の合計金額+このグラフで最小費用流を流して出た費用が答えになる。ただしグラフに負閉路があるので適当に工夫すること。
