UTPC2012 : J - きたまさの逆襲

ここまで来ると解き方が思いつかないのでもう実装練習。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_10

問題がややこしいが、

• ある鍵は１つの店にしかなく、その価格は決まっている。その鍵は１つで複数の宝箱のうち１つを開けられる。
• 各店iは、Bi円で店中の鍵の値段を1円上げられる。

このときに、全部の宝箱を開けるとき、(購入者の支払金額)-(店の引き上げにかかった金額和)を最大化する問題。

smallの場合、店は1つだけ。
そのため、鍵の値段を1円つり上げると、購入者が払う金額は宝箱の数Nと同じだけの鍵の分余分に払い、店はBi円余分に払うことになる。
よって、N > Biならいくらでも引き上げられる。N<=Biなら引き上げても無駄。
そのため後者の場合は単なる最小コストフローを求める問題となる。

ここまで考えて力尽きた。最小コストフローを求める方法を知らなかった。
そこで、蟻本を見ながら最小コストフローを作り、まずはsmallを解いてみた。
始点(0)→鍵集合(1～M)→宝箱集合(M+1～M+N)→終点(M+N+1)
となるようなグラフを作る。始点→鍵と宝箱→終点は容量1、コスト0とし、鍵集合→宝箱集合の辺は容量1、コストをCiとすればよい。

int N,M,D;

class MinCostFlow {
public:
	struct edge { int to, capacity, cost, reve;};
	static const int MV = 5000;
	vector<edge> E[MV];
	int dist[MV], prev_v[MV], prev_e[MV], NV;
	
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, int cap, int cost) {
		E[x].push_back((edge){y,cap,cost,E[y].size()});
		E[y].push_back((edge){x,0, -cost,E[x].size()-1}); /* rev edge */
	}
	
	int mincost(int from, int to, int flow) {
		int res=0,i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, 1<<29);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==1<<29) continue;
					FOR(i,E[v].size()) {
						edge &e=E[v][i];
						if(e.capacity>0 && dist[e.to]>dist[v]+e.cost) {
							dist[e.to]=dist[v]+e.cost;
							prev_v[e.to]=v;
							prev_e[e.to]=i;
							up=true;
						}
					}
				}
			}
			
			if(dist[to]==1<<29) return -1;
			int 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;
	}
};


void solve() {
	int x,y,i,j,res,TM,nc;
	int tx,ty,ng,LS;
	char cmd[100];
	ll p,cch;
	
	MinCostFlow g;
	GET3(&N,&M,&D);
	g.init(2+N+M);
	// 始点から鍵
	FOR(i,M) g.add_edge(0,1+i,1,0);
	// 宝箱から終点
	FOR(i,N) g.add_edge(1+M+i,1+M+N,1,0);
	
	FOR(i,M) {
		int cost = GETi();
		int shop = GETi()-1;
		
		// 鍵から宝箱
		int keys=GETi();
		FOR(j,keys) g.add_edge(1+i,1+M+(GETi()-1),1,cost);
	}
	
	// largeはあきらめる
	if(D>1) return;
	
	if(GETi()<N) _P("%d\n",-1);
	// N個の最小フロー
	else _P("%d\n",g.mincost(0,1+N+M,N));
	
	return;
}

続いてLarge。
先の議論を考えると、店が鍵価格を1円つり上げるのにBi円かかるなら、その店からBi円以下だけ購入するようにすればよい。
よって、下記の通りグラフを作りかえる。
始点(0)→店集合(1～D)→鍵集合(D+1～D+M)→宝箱集合(D+M+1～D+M+N)→終点(D+M+N+1)
ここで、始点→店集合の辺に、容量をBiにすればよい。
以下コード。MinCostFlowクラスは同じなので省略。

int N,M,D;

void solve() {
	int x,y,i,j,res,TM,nc;
	
	MinCostFlow g;
	GET3(&N,&M,&D);
	g.init(2+N+M+D);
	
	
	FOR(i,M) {
		int cost = GETi();
		int shop = GETi()-1;
		// 店から鍵
		g.add_edge(1+shop,1+D+i,1,cost);
		
		// 鍵から
		int keys=GETi();
		FOR(j,keys) g.add_edge(1+D+i,1+D+M+(GETi()-1),1,0);
	}
	// 始点から店
	FOR(i,D) g.add_edge(0,i+1,GETi(),0);
	// 宝から終点
	FOR(i,N) g.add_edge(1+D+M+i,1+D+M+N,1,0);
	
	_P("%d\n",g.mincost(0,1+N+M+D,N));
	
	return;
}

まとめ

コストや容量をうまく考えれば、最小フローであっさり解ける問題。
最小フローのライブラリも作るいい機会になったし、面白い問題だった。
ただ、パラメータが多くて問題の理解に苦労した…。