TopCoder SRM 658 Div1 Hard DancingForever

実装はラクという意味で850ptだけど、理解は難しい。
http://community.topcoder.com/stat?c=problem_statement&pm=13760

問題

N人の男性とN人の女性がいる。
N*Nの行列で各男性がどの女性をお気に入りかが与えられる。
(男性は最低1人以上お気に入りの女性がいる)

ここから男女の組を幾つか選んでダンスパーティーを行いたい。
ダンスに参加した男性がお気に入りの女性は、全てダンスに参加している、という条件を満たすような組み合わせが存在すればそれを1つ以上答えよ。

解法

自力では解けなかったので、下記を見て回答。
Short Editorial of SRM 658 Div1 - Codeforces

まず以下のグラフを作って最大フローを流す。

• Sourceから各男性に容量1の辺を張る
• 各男性からお気に入りの女性に容量無限の辺を張る
• 各女性からSinkに容量1の辺を張る

このフローは最大マッチングそのものである。
よってマッチング数がNなら、この時のマッチングが即解になる。

ただ、この問題は最大マッチングを求めたいわけではないため、マッチング数がN未満ならもう少し処理が必要である。
このグラフの残余グラフについて、Sourceから到達可能な頂点をDFS等で列挙する。

今後は以下のグラフを作って最大フローを流せばよい。
これは単なる2部グラフの最大マッチングを求めているだけである。

• Sourceから前処理で到達可能な各男性に容量1の辺を張る
• 各男性からお気に入りの女性に、双方が前処理で到達可能なら容量1の辺を張る
• 前処理で到達可能な各女性からSinkに容量1の辺を張る

なぜこれで良いかを考えてみる。
DFSで求めた頂点群は、最小カットでSource側に入る頂点群である。
これらの頂点群の集合のうち、男性側をB、女性側をGとする。
Bから到達可能な頂点群はGに含まれる。
また、各男性は最低1人はお気に入りの女性がいることから、Gに含まれる女性は必ず1人以上の男性とマッチングする。

よって2つ目のグラフの最大マッチングは|G|となり、Gの全員がダンスをすることになる。
またBの各人はG外の女性にお気に入りがいないことから、題意を満たすダンスの組み合わせが成立する。

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};

class DancingForever {
	public:
	int vis[203];
	int N;
	string X;
	void dfs(int cur,MaxFlow_Ford<int>& mf) {
		vis[cur]=1;
		FORR(r,mf.E[cur]) if(r.cap>0 && vis[r.to]==0) dfs(r.to,mf);
	}
	
	vector <int> getStablePairs(string X) {
		int i,x,y;
		N=sqrt(X.size()+0.1);
		this->X=X;
		
		MaxFlow_Ford<int> mf,mf2;
		FOR(i,N) mf.add_edge(0,i+1,1);
		FOR(i,N) mf.add_edge(i+101,202,1);
		FOR(x,N) FOR(y,N) if(X[x*N+y]=='Y') mf.add_edge(x+1,y+101,200);
		x=mf.maxflow(0,202);
		
		ZERO(vis);
		if(x==N) {
			FOR(i,N) vis[i+1]=vis[101+i]=1;
		}
		else {
			dfs(0,mf);
		}
		
		vector<int> R;
		FOR(i,N) if(vis[1+i]) mf2.add_edge(0,i+1,1);
		FOR(i,N) if(vis[101+i]) mf2.add_edge(i+101,202,1);
		FOR(x,N) FOR(y,N) if(X[x*N+y]=='Y' && vis[1+x]) mf2.add_edge(x+1,y+101,1);
		mf2.maxflow(0,202);
		FOR(i,N) FORR(r,mf2.E[i+1]) if(vis[1+i] && r.to>=101 && r.cap==0) R.push_back(i),R.push_back(r.to-101);
		
		return R;
	}
}

まとめ

最近結婚定理を使う問題が多いな。