kmjp's blog

競技プログラミング参加記です

TopCoder SRM 647 Div1 Hard ConvenientBlock

最小カットの勉強になった。
http://community.topcoder.com/stat?c=problem_statement&pm=13558

問題

0~(N-1)番のN頂点からなる有向グラフが与えられる。
0番から(N-1)番に至るパスの何か所かを監視することで、0番から(N-1)番に移動する際にどのようなパスを通ったとしても、ちょうど1回だけ監視されたパスを通るようにしたい。

各辺の監視コストが与えられるので、題意を満たす総監視コストの最小値を答えよ。

解法

一見単なる最小カット問題に見えるが、test case #0を試してみると分かるように単なる最小カットではうまく行かない。
test case #0でs→tの最小カットを求めた場合、1か所t→sとカットを逆流する辺が残ってしまう。
つまり、その逆流辺をたどることでs→tカットの境界を2回以上またぐことができてしまう。
これは問題の「ちょうど1回だけ監視されたパスを通る」に反する。

そこで、一度t側の頂点に到達したら、s側に逆流できないようにカットを選ばなければならない。
もともとある辺に対し、逆向きの容量無限大の辺を追加することで逆流を防ぐことができる。
なぜなら、仮に逆流できる辺がある場合、逆向きに容量無限大の辺があればそこは最小カットになりえないからである。

このように既存の辺に逆向きの容量無限大の辺を追加して、最小カットを求めればよいが、もう一つやることがある。
s→x←tのような頂点xがある場合、このグラフではsからtにフローが流せないが、容量無限大の辺を追加することでsからtにフローが流せるようになってしまう。
そこで、もともと到達不能な点・辺は外しておくと良い。

まとめると、到達不能な点・辺を外したうえで、既存の辺に逆向きの容量無限大の辺を追加し、最小カットを求めればよい。

template<class V> class MaxFlow_dinic {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 1100;
	vector<edge> E[MV];
	int itr[MV],lev[MV];
	
	void add_edge(int x,int y,V cap) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,0}); // directed
	}
	
	void bfs(int cur) {
		MINUS(lev);
		queue<int> q;
		lev[cur]=0;
		q.push(cur);
		while(q.size()) {
			int v=q.front(); q.pop();
			ITR(e,E[v]) if(e->cap>0 && lev[e->to]<0) lev[e->to]=lev[v]+1, q.push(e->to);
		}
	}
	
	V dfs(int from,int to,V cf) {
		if(from==to) return cf;
		ITR(e,E[from]) if(e->cap>0 && lev[from]<lev[e->to]) {
			V f=dfs(e->to,to,min(cf,e->cap));
			if(f>0) {
				e->cap-=f;
				E[e->to][e->reve].cap += f;
				return f;
			}
		}
		return 0;
	}
	
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			bfs(from);
			if(lev[to]<0) return fl;
			ZERO(itr);
			while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf;
		}
	}
};

int co[101][101];
const ll mama=1LL<<50;
class ConvenientBlock {
	public:
	long long minCost(int N, vector <int> from, vector <int> to, vector <int> cost) {
		int i,x,y;
		
		ZERO(co);
		FOR(x,N) co[x][x]=1;
		
		FOR(i,from.size()) co[from[i]][to[i]]=1;
		FOR(i,N) FOR(x,N) FOR(y,N) co[x][y]|=co[x][i]&&co[i][y];
		
		MaxFlow_dinic<ll> mf;
		FOR(i,from.size()) {
			if(co[0][from[i]]==0) continue;
			if(co[to[i]][N-1]==0) continue;
			mf.add_edge(from[i],to[i],cost[i]);
			mf.add_edge(to[i],from[i],mama);
			
		}
		
		ll m=mf.maxflow(0,N-1);
		return (m<mama)?m:-1;
	}
}

まとめ

解答見ても、最初なんで逆向きの辺を追加することで複数回の監視を防止できるかわからなかった。
最小カットの理解を深める良い機会になりました。