题意分析

题意简述

本题背景是在奶酪厂里，部分奶酪被机器操作后感染了。机器有 $N$ 个开关，每个开关可设为 $1$、$0$ 或 $*$（$*$ 表示该位可以看作 $0$ 或 $1$）。每次操作时，机器的状态对应着一组奶酪编号。如果状态中有 $*$，一次操作可以同时清理两块奶酪，这两块奶酪的编号仅在 $*$ 那一位上不同。

题目要求在不影响未被感染的奶酪的前提下，用最少的操作次数清理掉所有被感染的奶酪。也就是说，需要选择合适的操作，使得一次操作能尽可能多地清理感染奶酪，从而减少总的清理次数。

解题思路

• 1、确定被感染奶酪的集合
  对于每个输入的状态字符串，通过两种方式构造出对应的二进制编号（将 $*$ 分别看作 $0$ 和 $1$），放入集合中去重。

• 2、构图

  净化机一次操作最多允许一个 $*$，因此一次操作最多能清理两块奶酪，这两个编号只在 $*$ 所在位上不同。因此可以构造一个图，顶点为被感染奶酪的二进制编号，如果两个编号仅相差一位，则在它们之间连一条边，令图中每个节点表示一个被感染的奶酪编号。对任意两节点，若它们的异或值 $k = t[i] \oplus t[j]$ 不为 $0$ 且满足

  $$k \,\&\, (k-1) = 0,$$

  即 $k$ 为 $2^p$（表示两个编号恰好在一位不同），则在这两个节点间连一条边。

• 3、求最大匹配
  利用 DFS 实现的二分图匹配算法求出图中的最大匹配数。由于奶酪编号构成的图天然是二分图（不同编号的二进制数在翻转一位时会改变奇偶性），可以采用标准的二分匹配方法。

• 4、输出最少操作次数
  最少操作次数 $= cnt - \frac{\text{匹配数}}{2}$。
  由于匹配过程可能双向计数，最终需除以 $2$。

本题代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;

const int maxn = 2001;
int t[maxn], cnt = 0, n, m;
bool vis[maxn];
bool a[maxn][maxn] = {0};
int shu[maxn] = {0};
char s[50];
map<int, bool> mp;

bool dfs(int i) {
    for(int j = 1; j <= cnt; j++) {
        if(a[i][j] && !vis[j]) {
            vis[j] = true;
            if(!shu[j] || dfs(shu[j])) {
                shu[j] = i;
                return true;
            }
        }
    }
    return false;
}

void read() {
    cin >> s;
    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum = sum * 2 + (s[i] == '*' ? 0 : s[i] - '0');
    }
    if(!mp[sum]) {
        cnt++;
        mp[sum] = true;
        t[cnt] = sum;
    }
    sum = 0;
    for(int i = 0; i < n; i++) {
        sum = sum * 2 + (s[i] == '*' ? 1 : s[i] - '0');
    }
    if(!mp[sum]) {
        cnt++;
        mp[sum] = true;
        t[cnt] = sum;
    }
}

int main(){
    while(cin >> n >> m) {
        if(n == 0 && m == 0) break;
        memset(a, 0, sizeof(a));
        mp.clear(); cnt = 0;
        for(int i = 1; i <= m; i++)
            read();
        for(int i = 1; i <= cnt; i++){
            for(int j = i + 1; j <= cnt; j++){
                int k = t[i] ^ t[j];
                if(k && (k & (k - 1)) == 0)
                    a[i][j] = a[j][i] = true;
            }
        }
        int ans = 0;
        memset(shu, 0, sizeof(shu));
        for(int i = 1; i <= cnt; i++){
            memset(vis, 0, sizeof(vis));
            if(dfs(i))
                ans++;
        }
        printf("%d\n", cnt - ans/2);
    }
    return 0;
}