POJ 2724 Purifying Machine

题目链接

题意：这题题意有点没看懂。看了别人的题解，

给出m串长度为n的01串。

有些串中可能包括，这种串能够表示两个串，为1 和为0。

反复的算一种。比方题目中01

100

011

就代表了四个01串

001

101

100

011

如今我们须要消灭掉全部的01串，消灭方式有两种：

1一次消灭一个串。

2假设两个串的区别仅仅有一位的话能够同一时候消灭这两个串。

问最少多少次操作能够消灭全部的01串

思路：把存在的二进制数保存下来，然后去重。然后建边，二进制相差1位的连边。然后求最大独立集，n - 最大匹配数

代码：

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 2005;

int s[N], n, m;

char str[15];

vector<int> g[N];

int bitcount(int x) {

	return x == 0 ? x : bitcount(x>>1) + (x&1);

}

int left[N], vis[N];

bool dfs(int u) {

	for (int i = 0; i < g[u].size(); i++) {

		int v = g[u][i];

		if (vis[v]) continue;

		vis[v] = 1;

		if (left[v] == -1 || dfs(left[v])) {

			left[v] = u;

			return true;

		}

	}

	return false;

}

int hungary() {

	int ans = 0;

	memset(left, -1, sizeof(left));

	for (int i = 0; i < n; i++) {

		memset(vis, 0, sizeof(vis));

		if (dfs(i)) ans++;

	}

	return ans;

}

int main() {

	while (~scanf("%d%d", &n, &m) && n) {

		n = 0;

		for (int i = 0; i < m; i++) {

			scanf("%s", str);

			int len = strlen(str);

			s[n] = 0;

			for (int j = len - 1; j >= 0; j--)

				s[n] = s[n] * 2 + (str[j] != '0');

			n++;

			for (int j = 0; j < len; j++) {

				if (str[j] == '*') {

					s[n] = s[n - 1];

					s[n] ^= (1<<j);

					n++;

				}

			}

		}

		sort(s, s + n);

		int tmp = 1;

		for (int i = 1; i < n; i++)

			if (s[i] != s[i - 1]) s[tmp++] = s[i];

		n = tmp;

		for (int i = 0; i < n; i++) {

			g[i].clear();

			for (int j = 0; j < i; j++) {

				if (bitcount(s[i]^s[j]) <= 1) {

					g[i].push_back(j);

					g[j].push_back(i);

				}

			}

		}

		printf("%d\n", n - hungary() / 2);

	}

	return 0;

}