TopCoder SRM 557 Div1 Medium Incubator

さてMedium。こちらは本番中「なんかマッチング問題に持ち込むんだろうなー」と思いつつうまく持ち込めず失敗した問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12080

N人のうち、誰が誰を愛するという関係表が与えられる。
だれかが魔法を使える場合、魔法を使える人から愛される人は保護された状態になる。
また、保護された人から愛される人も保護された状態になる。

この条件のもとで、魔法を使えてかつ保護されない人数を最大化し、その人数を求める。

まず、関係表から、魔法を使える人ごとに、直接および間接的に保護される人の関係をワーシャル-フロイド法で求める。
N<=50だからこの処理はO(N^3)で問題なく終わる。

魔法を使える人を1人選ぶと、その人に保護される人は魔法を使える対象として選択できなくなる。
今回の問題は、魔法を使える人数を最大化したいので、すべての人は魔法を使うか保護されるかのどちらかになる。
よって、この問題は最大被覆の数を求める問題…と考えるとうまくいかない（最小被覆なら最大マッチングと同じなので良いが）。

この問題は、二部グラフのantichain数を求める問題に還元できる。

ここで、下記TopCoderのForumを参考にすると、Dilworthの定理について言及されている。(Wikipediaより)下の記事がDilworthの定理がわかりやすい。
http://apps.topcoder.com/forums/?module=Thread&threadID=764659&start=0
http://people.math.gatech.edu/~spingarn/4580/summaries/dilworth.pdf

Dilworthの定理は、|点| - |マッチング数| = |chain数| = |antichain数|ってことでいいのかな。
結局|点| - |マッチング数|を求めればよい。

#define MV 50
int NV;
int edge[MV+1][MV+1];
int rev[MV+1];
int visited[MV+1];

int bip_dfs(int v) {
	int tv;
	FOR(tv,NV) {
		if(!edge[v][tv] || visited[tv]) continue;
		visited[tv] = 1;
		if(rev[tv]<0 || bip_dfs(rev[tv])) {
			rev[tv]=v;
			return 1;
		}
	}
	return 0;
}

int bip_match(){
	int i,match=0;
	
	FOR(i,NV) rev[i]=-1;
	FOR(i,NV) {
		ZERO(visited);
		match += bip_dfs(i);
	}
	return match;
}


class Incubator {
	public:
	int N;
	int mat[51][51];
	int prot[51][51];
	int ng[51][51];
	
	int st[51];
	queue<int> dfs;
	int maxMagicalGirls(vector <string> love) {
		int x,y,z,i;
		
		N=love.size();
		ZERO(prot);
		FOR(x,N) FOR(y,N) if(love[x][y]=='Y') prot[x][y]=1;
		FOR(x,N) FOR(y,N) FOR(z,N) prot[y][z] |= prot[y][x] & prot[x][z];
		
		NV=N;
		memmove(edge,prot,sizeof(prot));
		
		return N-bip_match();
		
	}
};

まとめ

２部グラフのマッチングは以前書いて忘れていたのでもう一度書いてみた。
TopCoderのForumでも言及されている通り、Dilworthの定理はGCJ2009でも登場している。
http://code.google.com/codejam/contest/204113/dashboard#s=a&a=2

自分も本番中この問題を思い出したのだが、GCJのはchain数の最小化、こちらは点被覆の最大化と認識してしまい、両者を結びつけられず答えまで行けなかった。
ちょっとまだDilworthの定理のあたりが理解できてないので、Editorial見て直すかも。