POJ 2724 Purifying Machine（最大獨立集）
來源：程序員人生 發布時間：2014-11-22 08:31:47 閱讀次數：3445次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
