このテクは知らなかった。
https://atcoder.jp/contests/arc125/tasks/arc125_e
問題
N種類のお菓子があり、i種類目のお菓子はA[i]個ある。
これらのお菓子をM人の子供に配る。ただし各子供jは、1種類のお菓子をB[j]個以下、合計でC[j]個しか受け取らない。
条件を満たしたうえで、子供に最大何個お菓子を配れるか。
解法
まず計算量は無視して、グラフの最大フロー問題としてこの問題を表現してみる。
- sourceからお菓子iに容量A[i]の辺を張る
- お菓子iから子供jにそれぞれ容量C[j]の辺を張る
- 子供jからsinkに容量B[j]の辺を張る
とすると、このグラフの最大フローは問題の解となる。
ただ、このグラフは辺がO(NM)本になるので、このままでは成り立たない。
そこで、このグラフの最小カットを求めよう。
お菓子のうちA[i]の大きいx個がカットのsource側に来るとする。
その場合、各子供はB[j]*xとC[j]のどちらが大きいかによって、source側とsink側どちら側に属するかが決まる。
あとは、xを総当たりしつつカットの大きさを求め、その最小値を解とすればよい。
int N,M; ll A[202020],B[202020],C[202020]; vector<int> step[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; ll SA=0; FOR(i,N) { cin>>A[i]; SA+=A[i]; } sort(A,A+N); reverse(A,A+N); ll SB=0; FOR(i,M) { cin>>B[i]; SB+=B[i]; } ll SC=0; FOR(i,M) { cin>>C[i]; if((C[i]+B[i]-1)/B[i]<=N) step[(C[i]+B[i]-1)/B[i]].push_back(i); } ll ret=1LL<<60; FOR(i,N+1) { FORR(e,step[i]) { SC+=C[e]; SB-=B[e]; } ret=min(ret,SA+SC+i*SB); SA-=A[i]; } cout<<ret<<endl; }
まとめ
勉強になりました。