传送
扒下来的题意：迈克有一台可以净化奶酪的机器，用二进制表示净化的奶酪的编号。但是，在某些二进制串中可能包含有\(*\)。例如\(01*100\)，\(*\)其实就代表可以取\(0\),\(1\)两种情况：\(010100\) 和\(011100\)。现在由于迈克不小心，他以同样的方式弄脏了某些奶酪，问你最少用多少次操作就可以把弄脏的奶酪全净化好。（没有被弄脏过的奶酪不能净化。弄脏过的奶酪可以多次净化。）
也就是给你一些不同的(判重之后)二进制串,每个串可以通过1次操作净化,也可以把两个只有1位不同的串通过1次操作联合净化.要我们求最少的操作次数.
这题刚开始比较好想：把所有的 ‘*‘ 拆成这一位分别是0和1的两个字符串，然后就要从这里面挑出最少数量的模板，使这些模板最多有一位是 ‘*‘ 的条件下能表示出所有串。
接下来的话，如果往图论方面想的话思路就通了。我们给只有一位不同的两个串互相连边，这样就相当于选择一个最大匹配\(p\)，那么答案就是\(n-p\)（即去重后的串总数减去能合并的串的个数）。
考虑互相连边的两个串：因为只有这一位不同，所以1的个数必然是奇偶不同的，因此这个图就是一个二分图，用匈牙利算法就解决了。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(‘ ‘)
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1050;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ‘ ‘;
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
if(las == ‘-‘) ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar(‘-‘);
if(x >= 10) write(x / 10);
putchar(x % 10 + ‘0‘);
}
char s[maxn];
int n, m, N, cnt = 0;
int a[maxn], G[maxn][maxn];
In void buildGraph()
{
for(int i = 1; i <= m; ++i)
{
scanf("%s", s);
int len = strlen(s), pos = -1, tp = 0;
for(int j = 0; j < len; ++j)
if(s[j] == ‘*‘) pos = j;
else if(s[j] == ‘1‘) tp |= (1 << j);
a[tp] = 1;
if(~pos) a[tp | (1 << pos)] = 1;
}
N = 1 << n, cnt = 0;
for(int i = 0; i < N; ++i) if(a[i])
{
++cnt;
for(int j = 0; j < n; ++j)
{
int tp = i ^ (1 << j);
if(a[tp]) G[i][tp] = 1;
}
}
}
bool vis[maxn];
int fa[maxn];
In bool dfs(int now)
{
for(int i = 0; i < N; ++i)
if(a[i] && !vis[i])
{
vis[i] = 1;
if(fa[i] == -1 || dfs(fa[i])) {fa[i] = now; return 1;}
}
return 0;
}
In int solve()
{
Mem(fa, -1);
int ret = 0;
for(int i = 0; i < N; ++i) if(a[i])
{
Mem(vis, 0);
if(dfs(i)) ++ret;
}
return cnt - ret / 2;
}
In void init()
{
Mem(a, 0), Mem(G, 0);
}
int main()
{
while(scanf("%d%d", &n, &m) && (n | m))
{
init();
buildGraph();
write(solve()), enter;
}
return 0;
}