净水机器(Purifying Machine) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m && (n != 0 || m != 0)) {
        int lim = 1 << n;
        vector<int> has(lim, 0);
        for (int i = 0; i < m; ++i) {
            string s;
            cin >> s;
            int val = 0, star = -1;
            for (int j = 0; j < n; ++j) {
                if (s[j] == '1') val |= (1 << j);
                else if (s[j] == '*') star = j;
            }
            has[val] = 1;
            if (star != -1) {
                has[val | (1 << star)] = 1;
            }
        }
        vector<int> nodes;
        for (int x = 0; x < lim; ++x) {
            if (has[x]) nodes.push_back(x);
        }
        int V = nodes.size();
        vector<vector<int>> adj(V);
        for (int i = 0; i < V; ++i) {
            if (__builtin_popcount(nodes[i]) % 2 != 0) continue;
            for (int j = 0; j < V; ++j) {
                int diff = nodes[i] ^ nodes[j];
                if (diff != 0 && (diff & (diff - 1)) == 0) {
                    adj[i].push_back(j);
                }
            }
        }
        vector<int> matchR(V, -1), vis(V, -1);
        auto dfs = [&](auto& self, int u, int stamp) -> bool {
            for (int v : adj[u]) {
                if (vis[v] == stamp) continue;
                vis[v] = stamp;
                if (matchR[v] == -1 || self(self, matchR[v], stamp)) {
                    matchR[v] = u;
                    return true;
                }
            }
            return false;
        };
        int matched = 0;
        for (int i = 0; i < V; ++i) {
            if (__builtin_popcount(nodes[i]) % 2 == 0) {
                if (dfs(dfs, i, i)) matched++;
            }
        }
        cout << (V - matched) << "\n";
    }
    return 0;
}