kmjp's blog

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

ABBYY Cup 3.0 : C. Tidying Up

ここからは難しいので解説を参考に。
http://codeforces.com/contest/316/problem/C2

問題

N*Mのマス目に、N*M/2種類の靴が2個ずつ置いてある。
この状態で、各靴のペアが隣接マスに来るようにするための位置を動かさないといけない靴の数の最小値を答えよ。

解法

よくあるマス目に1*2のブロックを敷き詰める問題に似ている。

各マスを(i,j)として、ペアの片方はi+jが偶数、もう片方は奇数となる。
よって、偶数マスから4つの奇数マスに辺を張り、最小コストフローを解けばよい。
隣接マスがすでに同じ靴ならコスト0、異なるならコスト1である。

int W,H;
int A[100][100];

class MinCostFlow {
public:
	struct edge { int to, capacity, cost, reve;};
	static const int MV = 7000;
	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 f,r,i,j,k,l, x,y;
	int q=0;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) A[y][x]=GETi();
	MinCostFlow mcf;
	mcf.init(H*W+2);
	FOR(y,H) FOR(x,W) {
		if((y+x)%2) {
			mcf.add_edge(0,y*W+x+1,1,0);
			if(x>0)   mcf.add_edge(y*W+x+1,y    *W+x+0,1,A[y][x]!=A[y][x-1]);
			if(x<W-1) mcf.add_edge(y*W+x+1,y    *W+x+2,1,A[y][x]!=A[y][x+1]);
			if(y>0)   mcf.add_edge(y*W+x+1,(y-1)*W+x+1,1,A[y][x]!=A[y-1][x]);
			if(y<H-1) mcf.add_edge(y*W+x+1,(y+1)*W+x+1,1,A[y][x]!=A[y+1][x]);
		}
		else {
			mcf.add_edge(y*W+x+1,W*H+1,1,0);
		}
	}
	
	_P("%d\n",mcf.mincost(0,W*H+1,W*H/2));
	return;
}

まとめ

2マスのものを敷き詰めるときは、i+jの偶奇を気にしないとね。