输入:
7 39
1100110
0100101
0101100
0100010
0010111
*011001
1110110
0101010
0001000
10*0001
1010101
0111000
1011011
0010101
0110101
1101011
0001110
1001101
1111011
0001101
0011101
0000101
1111100
0111001
0101001
11100*0
0000110
0001111
1101001
0010011
11*0000
0000111
1*00000
1000101
001*100
101000*
1111010
000110*
0010010
0 0
答案:
23

My output:
22

#include<iostream>
#include<climits>
#include<cstring>
#include<cstdio>
#include<queue>
// #define ls(i) (i)
// #define rs(i) (i+N)
using namespace std;
const int MAXN = 2e3+10;
const int MAXM = 4e6+10;
struct node
{
    int from, to;
    int flow;
    int next;
}a[MAXM];
int n, m, N, s = 2001, t = 2002, x[MAXN];
int maxflow, nowflow, vis[MAXN], col[MAXN];
int head[MAXN], cnt = 1, as[2048];
char ch[MAXN][15];
auto work() -> void;
auto bfs(int s, int t) -> bool;
auto check(int x, int y) -> bool;
auto dfs(int x, int color) -> void;
auto dinic(int x, int flow) -> int;
auto Add_edge(int from ,int to, int flow) -> void;
auto add_edge(int from, int to, int flow) -> void;
int main()
{
    // freopen("2.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    scanf("%d%d", &n, &m);
    while(n or m) work(), scanf("%d%d", &n, &m);
    return 0;
}
auto work() -> void
{
    memset(x, 0, sizeof(x));
    memset(as, 0, sizeof(as));
    memset(vis, 0, sizeof(vis));
    memset(head, 0, sizeof(head)); 

    cnt = 1; N = 0; maxflow = 0;

    for(int i = 1; i <= m; i += 1)
        scanf("%s", ch[i]+1);

    for(int i = 1; i <= m; i += 1)
    {
        int a = 0, b = 0;

        for(int j = 1; j <= n; j += 1)
        {
            if(ch[i][j] == '0') a <<= 1, b <<= 1;
            else if(ch[i][j] == '1') a = (a<<1)|1, b = (b<<1)|1;
            else if(ch[i][j] == '*') a = (a<<1)|1, b = b<<1;
        }

        if(!as[a]) as[a] = 1, x[++N] = a;
        if(!as[b]) as[b] = 1, x[++N] = b;
    }
    // for(int i = 1; i <= 1024; i += 1)
    //     if(as[i]) x[++N] = i;
    for(int i = 1; i <= N; i += 1)
        for(int j = i+1; j <= N; j += 1)
            if(check(i, j)) add_edge(i, j, 1), add_edge(j, i, 1);

    for(int i = 1; i <= N; i += 1)
        if(!vis[i]) dfs(i, 0);
    s = N + 1, t = N + 2;

    for(int i = 1; i <= N; i += 1)
    {
        if(col[i]) add_edge(s, i, 1);
        else add_edge(i, t, 1);
    }

    while(bfs(s, t))
        while((nowflow = dinic(s, INT_MAX)))
            maxflow += nowflow;

    printf("%d\n", N-maxflow);
}
auto check(int i, int j) -> bool
{
    int k = x[i]^x[j];
    return k and (k == (k&-k));
}
auto add_edge(int from, int to, int flow) -> void
{
    Add_edge(from, to, flow);
    Add_edge(to, from, 0);
}
auto Add_edge(int from, int to, int flow) -> void
{
    cnt += 1;
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].flow = flow;
    a[cnt].next = head[from];
    head[from] = cnt;
}
auto bfs(int s, int t) -> bool
{
    memset(vis, 0, sizeof(vis));
    queue<int> q; q.push(s);
    vis[s] = 1; int x, y;
    while(!q.empty())
    {
        x = q.front(); q.pop();
        for(int i = head[x]; i; i = a[i].next)
        {
            y = a[i].to;
            if(!vis[y] and a[i].flow)
            {
                vis[y] = vis[x]+1;
                if(y == t) return true;
                q.push(y);
            }
        }
    }
    return false;
}
auto dinic(int x, int flow) -> int
{
    if(x == t) return flow;
    int rest = flow, y, k;
    for(int i = head[x]; i; i = a[i].next)
    {
        y = a[i].to;
        if(vis[y] == vis[x]+1 and a[i].flow)
        {
            k = dinic(y, min(rest, a[i].flow));
            if(!k) vis[y] = 0;
            a[i].flow -= k;
            a[i^1].flow += k;
            if(!(rest-=k)) break;
        }
    }
    return flow-rest;
}
auto dfs(int x, int color) -> void
{
    vis[x] = 1;
    col[x] = color;
    for(int i = head[x]; i; i = a[i].next)
    {
        int y = a[i].to;
        if(!vis[y]) dfs(y, 1-color);
    }
}