TopCoder SRM 557 Div1 Medium Incubator

問題

少女がn人いて、i番目の少女がj番目の少女を愛しているかのグラフが与えられる。
グラフは対称ではない。

このグラフに対して以下の操作を好きなだけ行うことができる。
初期状態で、全ての少女は魔法少女ではなく、護られている少女ではない。

• 魔法少女でない少女を一人選び、魔法少女にする。
• 魔法少女が好きな少女はみな護られている少女になる。
• 護られている少女が好きな少女はみな護られている少女になる。

操作が終わったあとで、魔法少女であり、
誰かに護られていない少女の数を最大にしたい。
この最大値を求めよ。

制約条件

n≦50

方針

少女i魔法少女にすると、iから辿れるノード全てが護られる。
また、iに至るノード全てが選べなくなる（選んでも答えが増えなくなる）。

すなわち、iに弱連結であるようなノードが選べなくなる。
自分から出て自分に帰ってくるような閉路があるノードは選んでも意味がない。
なので、全て消しておく。

すると、残ったグラフはDAGなので、DAG上で弱連結でないノードの集合の大きさの最大値を求めればよい。
これはDilworthの定理より、DAGの推移閉包を取ったものの最小パス被覆の大きさに等しい。

最小パス被覆は、グラフを2部グラフ化して最大マッチングを求めればよい。

ソースコード

int n;
bool use[50], v[100];
bool e[100][100], g[50][50];
int p[100];
bool match(int s){
	if(s < 0) return 1;
	rep(i, 2 * n) if(!v[i] && e[s][i]){
		v[i] = 1;
		if(match(p[i])) return p[i] = s, p[s] = i, 1;
	}
	return 0;
}
class Incubator {
	public:
	int maxMagicalGirls(vector <string> love) {
		n = love.size();
		rep(i, n) rep(j, n) g[i][j] = e[i][j] = love[i][j] == 'Y';
		rep(k, n) rep(i, n) rep(j, n) g[i][j] |= g[i][k] && g[k][j];
		rep(i, n) use[i] = !g[i][i];
		
		memset(e, 0, sizeof(e));
		memset(p, -1, sizeof(p));
		rep(i, n) rep(j, n) if(use[i] && use[j] && g[i][j]) e[i][j + n] = e[j + n][i] = 1;
		
		int ans = 0;
		rep(i, n) if(use[i]) ans++;
		rep(i, 2 * n) if(p[i] < 0){
			memset(v, 0, sizeof(v));
			if(match(i)) ans--;
		}
		return ans;
	}
};