Codeforces #212 Div2. E. Petya and Pipes

これは本番、MinCostFlowを使えばいいんじゃね？という発想までは行ったけど結局辺の張り方がわかんなかった問題。
結局Editorialを見て解いた。
http://codeforces.com/contest/362/problem/E

問題

N個の町の間に向きのある水道管がいくつかあり、町iから町jにつながる各水道管は秒間C[i][j]の水を流すことができる。
ここで、町0から町(N-1)に流す水の量を最大にしたい。
すでに水道管が張られている場所について、その水道管の容量をコスト1で1だけ増やすことができる。
最大コストKが与えられたとき、K以下のコストで流せる最大水量を答えよ。

解法

問題からすると最大フロー問題に見えるが、コストを抑える問題なので最小コストフロー問題になる。
各水道管に対して、以下の2辺を張ったグラフを考える。

• 点iから点jへの、容量C[i][j]、コスト0の辺
• 点iから点jへの、容量無限大、コスト1の辺

このように辺を張ると、容量C[i][j]まではコスト0、それ以上はコストを払えばその分多くの容量を流すことができる。
あとは、流す水量を二分探索し、コストをK以下にできる最大水量を求めればよい。

1点注意点は、もともと水道管がない場所に水道管を張ることはできないので、初期状態で町0から(N-1)に水を1も流せない場合、そもそも水道管がないのでコストを払っても水は流せない。

class MinCostFlow {
public:
	struct edge { int to, capacity; ll cost, reve;};
	static const int MV = 5000;
	vector<edge> E[MV];
	ll 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, 1LL<<50);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==1LL<<50) 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]==1LL<<50) 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 f,i,j,k,l,x,y;
	int N,K;
	MinCostFlow mcf,mcf2;
	
	cin>>N>>K;
	mcf.init(N);
	FOR(y,N) FOR(x,N) {
		cin>>i;
		if(i) {
			mcf.add_edge(y,x,i,0);
			mcf.add_edge(y,x,1<<28,1);
		}
	}
	
	mcf2=mcf;
	if(mcf2.mincost(0,N-1,1)<0) return _P("0\n");
	
	mcf2=mcf;
	int lo=0,hi=1<<27;
	FOR(i,40) {
		int po=(lo+hi)/2;
		if(lo==hi) break;
		mcf=mcf2;
		if(mcf.mincost(0,N-1,po)>K) hi=po-1;
		else lo=po;
	}
	
	lo=max(0,lo-3);
	i=0;
	while(1) {
		mcf=mcf2;
		if(mcf.mincost(0,N-1,lo)>K) break;
		lo++;
	}
	_P("%d\n",lo-1);
}

まとめ

「コストを払ってフローを増やす」という問題に、この2辺を張るアイデアは応用できそうだ。