POJ 2724 Purifying Machine（最大独立集）
来源：程序员人生 发布时间：2014-11-22 08:31:47 阅读次数：3279次
POJ 2724 Purifying Machine
题目链接
题意：这题题意有点没看懂，看了他人的题解，
给出m串长度为n的01串。有些串中可能包括，这样的串可以表示两个串，为1 和为0。重复的算1种。比如题目中01
100
011
就代表了4个01串
001
101
100
011
现在我们需要消灭掉所有的01串，消灭方式有两种：
11次消灭1个串。
2如果两个串的差别只有1位的话可以同时消灭这两个串。
问最少多少次操作可以消灭所有的01串
思路：把存在的2进制数保存下来，然后去重，然后建边，2进制相差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] == ⑴ || dfs(left[v])) {
left[v] = u;
return true;
}
}
return false;
}
int hungary() {
int ans = 0;
memset(left, ⑴, 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 - hungary() / 2);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
