久々にSRMで最小コストフローか?
https://community.topcoder.com/stat?c=problem_statement&pm=15702
問題
N種類のシャツと、M種類のジーンズがあり、それぞれの価値が与えられる。
また、シャツとジーンズの組み合わせD種がある。
D種中K種選んだ時、1回以上含まれるシャツとジーンズの価値の最大値を求めよ。
解法
最小コストフローで解く。
source→(N個のシャツ)→(M個のジーンズ)→sink
の順で辺を張る。
source→シャツの辺は、容量1・コスト(10^6-価値)の辺と、容量∞・コスト10^6の辺を2種類張る。
そうすると、初めてそのシャツを使われるときだけコストが低いことになる。
同様にジーンズ→sinkも2種類の辺を張る。
シャツとジーンズの間は、D種類に対応する辺を張る。これは容量∞・コスト0でよい。
このグラフにフローDを流し、(2*D*10^6)-(最小コスト)を答えればよい。
template<int NV,class V> class MinCostFlow { public: struct edge { int to; V capacity; V cost; int reve;}; vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV]; void add_edge(int x,int y, V cap, V cost) { E[x].push_back((edge){y,cap,cost,(int)E[y].size()}); E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */ } V mincost(int from, int to, ll flow) { V res=0; int i,v; ZERO(prev_v); ZERO(prev_e); while(flow>0) { fill(dist, dist+NV, numeric_limits<V>::max()/2); dist[from]=0; priority_queue<pair<V,int> > Q; Q.push(make_pair(0,from)); while(Q.size()) { V d=-Q.top().first; int cur=Q.top().second; Q.pop(); if(dist[cur]!=d) continue; if(d==numeric_limits<V>::max()/2) break; FOR(i,E[cur].size()) { edge &e=E[cur][i]; if(e.capacity>0 && dist[e.to]>d+e.cost) { dist[e.to]=d+e.cost; prev_v[e.to]=cur; prev_e[e.to]=i; Q.push(make_pair(-dist[e.to],e.to)); } } } if(dist[to]==numeric_limits<V>::max()/2) return -1; ll lc=flow; for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity); flow -= lc; res += lc*dist[to]; for(v=to;v!=from;v=prev_v[v]) { edge &e=E[prev_v[v]][prev_e[v]]; e.capacity -= lc; E[v][e.reve].capacity += lc; } } return res; } }; class ShoppingSpree { public: int maxValue(int k, vector <int> shirtValue, vector <int> jeansValue, vector <int> shirtType, vector <int> jeansType) { MinCostFlow<250,ll> mcf; int N=shirtValue.size(); int M=jeansValue.size(); int D=shirtType.size(); int i; FOR(i,N) { mcf.add_edge(0,i+2,1,1000000-shirtValue[i]); mcf.add_edge(0,i+2,100,1000000); } FOR(i,M) { mcf.add_edge(i+102,1,1,1000000-jeansValue[i]); mcf.add_edge(i+102,1,100,1000000); } FOR(i,D) { mcf.add_edge(2+shirtType[i],102+jeansType[i],100,0); } return 2*k*1000000-mcf.mincost(0,1,k); } }
まとめ
450ptなこともあって、あんまり難しいフローじゃないね。