POJ 2724: Purifying Machine

http://poj.org/problem?id=2724

omochan.hatenablog.com
↑これとほとんど同じ。
一気に*を使って消せるやつ同士に辺を張ったグラフは2部グラフとなる。
2部グラフになるためには任意のサイクルの大きさが偶数であればよいが、Nコのbitのうち1つ変えるという作業を繰り返し行うとき、元に戻るためには偶数回である必要がある。よってこの条件を満たす。
あとはフローを流して最小辺カバーを求めれば良い。その際グラフの点の個数を二倍にすると楽。

二部グラフから考えるというよりは、このグラフの最大マッチング求めたいな…ところでこのグラフは二部グラフじゃん!みたいな感じかな。

int N, M;
char s[20];
bool MP[MAX_N][MAX_N];
bool A[MAX_N];

int main() {
	rep(bit, 0, (1 << 10)) {
		rep(i, 0, 10) {
			if(bit & (1 << i)) MP[bit][bit - (1 << i)] = true;
			else MP[bit][bit | (1 << i)] = true;
		}
	}

	while(true) {
		scanf("%d%d", &N, &M);
		if(N == 0 && M == 0) break;
		memset(A, 0, sizeof(A));

		rep(i, 0, M) {
			scanf("%s", s);
			int v1 = 0, v2 = 0;
			rep(i, 0, N) {
				if(s[i] == '*') v1 += (1 << i);
				else if(s[i] == '1') {
					v1 += (1 << i);
					v2 += (1 << i);
				}
			}
			A[v1] = true; A[v2] = true;
		}

		MF::init((1 << (N + 1)) + 2);
		int s = (1 << (N + 1)), t = (1 << (N + 1)) + 1;

		int V = 0;
		rep(i, 0, (1 << N)) {
			if(A[i]) {
				V++;
				MF::add_edge(s, i, 1);
				MF::add_edge(i + (1 << N), t, 1);
			}
		}

		rep(i, 0, (1 << N)) {
			if(!A[i]) continue;
			rep(j, 0, (1 << N)) {
				if(A[j] && MP[i][j]) {
					MF::add_edge(i, j + (1 << N), 1);
				}
			}
		}
		int ans = MF::get(s, t);
		printf("%d\n", V - ans / 2);
	}
			
	return 0;
}