kmjp's blog

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

TopCoderOpen 2013 Round1A Hard DirectionBoard

SRM

さてHard。本番中には解けなかったけど、終わってみて再チャレンジしたらすぐ解けた。
そんな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12390

問題

平面上の各マスに、上下左右のいずれかを向いた矢印がある。
各マスから開始して、矢印を順次たどると元の場所に戻ってくるようにしたい。
そのために向きを変えなければいけない矢印の数を答える。
なお、平面の上下左右はループしている。

解法

本番中に、各マスに入る矢印が１つだけなら題意を満たすことに気づいた。
各マスに入る矢印が１つなら、途中で始点に戻らないループに陥ることなくいずれ始点にたどりつく。
ただ、そのためにどう矢印を動かせばいいかわからなかった。
「最大フローとか使うのかなー」とか思ってたら時間終了。

終わってから他人の回答見て気づいた。最小費用流使ってる…。
最小費用流ということに気づいたらすぐ解ける。

答えは、以下の様に作成したグラフにおいて、Nのフローを流す場合の最小費用となる。
まず、sink(V[0])からW*H=N個のマス(V[1]～V[N]に対応する点への辺を張る。
この辺は容量1、コスト0である。

また、それとは別にまたN個のマス(V[N+1]～V[2N])に点を作る。
そして、V[1]～V[N]点から、その上下左右のマスに対応する点(V[N+1]～V[2N])へ辺を張る。
この各辺はいずれも容量は1だが、コストはすでに矢印が向いてる方は0、それ以外は1とする。
そして最後にV[N+1]～V[2N]の点から、targetの点V[2N+1]に辺を張ればよい。

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;
	}
};

class DirectionBoard {
	public:
	
	int W,H;
	int getMinimum(vector <string> board) {
		int x,y;
		H=board.size();
		W=board[0].size();
		MinCostFlow mcf;
		
		mcf.init(2+2*H*W);
		
		FOR(y,H) FOR(x,W) {
			mcf.add_edge(0,1+y*W+x,1,0);
			mcf.add_edge(1+(H*W)+y*W+x,1+2*(H*W),1,0);
			
			mcf.add_edge(1+y*W+x,1+(H*W)+y*W+((x+W-1)%W),1,(board[y][x]=='L')?0:1);
			mcf.add_edge(1+y*W+x,1+(H*W)+y*W+((x+1)%W),1,(board[y][x]=='R')?0:1);
			mcf.add_edge(1+y*W+x,1+(H*W)+(y+H-1)%H*W+x,1,(board[y][x]=='U')?0:1);
			mcf.add_edge(1+y*W+x,1+(H*W)+(y+1)%H*W+x,1,(board[y][x]=='D')?0:1);
			
		}
		
		return mcf.mincost(0,1+2*(H*W),(H*W));
	}

};

まとめ

最小費用流は以前ライブラリにしていたので、気づいたらすぐに回答できた。
あとは、本番に「最大フローかな？」と思った時に最小費用流に持ち込む部分ができてればなぁ。

それにしても、マス目の問題がグラフ問題に落とし込めるというのは面白いな。