TopCoder SRM 612 Div1 Medium SpecialCells

正直この問題の最大の敵は問題文…。
http://community.topcoder.com/stat?c=problem_statement&pm=12354

問題

2次元座標上にN個の点が与えられる。

ここで、これらの点の座標をシャッフルする。
シャッフルとはN点のX座標とY座標の対応をN点間で入れ替えることである。

シャッフル後のN点が、できるだけ元のN点と一致しないようにしたい。
一致してしまう点の数を最小化せよ。

解法

マッチング＋最小化ということで最小コストフローで解くことができる。
まず、sourceからX座標に対応する点にN点中そのX座標が登場する分の帯域だけ辺を張る。
同様にY座標に対応するからtargetに同様に辺を張る。

次にこれらのX座標とY座標に対応する点の間で辺を張るわけだが、(X座標,Y座標)に対応する点がもともとN点にある場合は帯域1,コスト1、N点にない場合は帯域1,コスト0として辺を張る。

後は最小コストフローを解くだけ。
元のN点と同じ(X座標,Y座標)の点を選ぶことはコスト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;
	}
};

class SpecialCells {
	public:
	int N;
	
	int guess(vector <int> X, vector <int> Y) {
		int i,j,x,y;
		vector<int> X2,Y2;
		
		N=X.size();
		map<int,int> mx,my;
		set<int,int> e;
		ITR(it,X) mx[*it]=0;
		ITR(it,Y) my[*it]=0;
		i=j=0;
		ITR(it,mx) it->second=i++;
		ITR(it,my) it->second=j++;
		
		int cx[50],cy[50],cxy[50][50];
		ZERO(cx);
		ZERO(cy);
		ZERO(cxy);
		
		FOR(i,N) {
			cx[mx[X[i]]]++;
			cy[my[Y[i]]]++;
			cxy[mx[X[i]]][my[Y[i]]]++;
		}
		
		MinCostFlow mcf;
		mcf.init(500);
		
		FOR(i,N) mcf.add_edge(0,100+i,cx[i],0);
		FOR(i,N) FOR(j,N) mcf.add_edge(100+i,200+j,1,cxy[i][j]);
		FOR(i,N) mcf.add_edge(200+i,1,cy[i],0);
		
		return mcf.mincost(0,1,N);
	}
};

まとめ

もともと誤解した問題設定においてもフローにはたどり着けていたし、問題文さえちゃんと読めていればかなりあっさり解けた問題…。
他にも同じように誤読した日本人が多かった様子。
ちゃんと問題文読まないとなぁ…。