POJ 2724 Purifying Machine(最大独立集)

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;
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。