POJ-2724 : Purifying Machine

問題概要

長さN(<10)のM(<1000)個の文字列で生成される数字がある。文字列は高々1個の*を含むビット列で、生成されるのはそれに対応する整数。生成された文字列と同じものをつくるビット列で文字列の個数は最小いくつ必要か求める問題。

解法

xorとってbitcountが1なら辺を張る。後は二部マッチングの分だけ減らすことができる。

acceptされたコード

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<int> bits;
char buf[0x100];

bool init() {
	scanf("%d%d ", &N, &M);
	bits.clear();
	for (int _ = 0; _ < M; ++_) {
		scanf(" %s ", buf);
		int t = 0;
		for (int i = 0; i < N; ++i) {
			if (buf[i] == '1') {
				t += 1<<(N-i-1);
			}
		}
		bits.push_back(t);
		for (int i = 0; i < N; ++i) {
			if (buf[i] == '*') {
				t += 1<<(N-i-1);
			}
 		}
		bits.push_back(t);
	}
	sort(bits.begin(), bits.end());
	bits.erase(unique(bits.begin(), bits.end()), bits.end());
	return N > 0 && M > 0;
}

int solve() {
	G.init(bits.size());
	for (int i = 0; i < (int)bits.size(); ++i) {
		for (int j = i + 1; j < (int)bits.size(); ++j) {
			int xo = bits[i] ^ bits[j];
			if ((xo & (-xo)) == xo) {
				G.addUndirectedEdge(i, j);
			}
		}
	}

	return G.numV - calcBipartiteMatching(G);
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}