[二分匹配]poj 2724：Purifying Machine

大致题意：

    给出m串长度为n的01串。有些串中可能包含*，这样的串可以表示两个串，*为1 和*为0。重复的算一种。比如题目中

*01

100

011

就代表了四个01串

001

101

100

011

现在我们需要消灭掉所有的01串，消灭方式有两种：

1一次消灭一个串。

2如果两个串的差别只有一位的话可以同时消灭这两个串。

 

问最少多少次操作可以消灭所有的01串

 

大致思路：
   按照串中1的个数的奇偶性把串分为两个集合，因为1的个数的奇偶性相同的两个串之间的差别数必然大于1。想到这里接下来就简单了。(吐槽，从昨晚wrong到现在，真心被wa到内伤了，不过ac的感觉很爽啊)

 

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=(1<<11)+10;
bool used[nMax];
int num[nMax],cnt;
char str[100];
bool map[nMax][nMax],vis[nMax];
int linkk[nMax],n,m,dd;

int dfs(int s){
    for(int i=0;i<cnt;i++){
        if(!vis[i]&&map[s][i]){
            vis[i]=1;
            if(linkk[i]==-1||dfs(linkk[i])){
                linkk[i]=s;
                return 1;
            }
        }
    }
    return 0;
}

void solve(int len){
    int i,a,b,c;
    a=b=c=0;
    for(i=0;i<len;i++){
        a<<=1;
        b<<=1;
        if(str[i]=='*'){
            a+=0;
            b+=1;
            c=1;
        }
        else{
            a+=str[i]-'0';
            b+=str[i]-'0';
        }
    }
    if(!used[a]){
      //  cout<<a<<endl;
        used[a]=1;
        num[cnt++]=a;
    }
    if(!used[b]){
   //     cout<<b<<endl;
        used[b]=1;
        num[cnt++]=b;
    }
}

//检查一个数的二进制中1的个数
int judge(int fuck){   
    int a=0;
    while(fuck){
        if(fuck&1)a++;
        fuck>>=1;
    }
    if(a&1)return 1;
    return 0;
}

void initmap(int nn){
    int i,j,a,b,c;
    memset(map,0,sizeof(map));
    for(i=0;i<cnt;i++){
        if(judge(num[i]))continue;
        for(j=0;j<cnt;j++){
            if(!judge(num[j]))continue;
            a=num[i]^num[j];
            if(a&&((a&(a-1))==0)){
                map[i][j]=1;
            }
        }
    }
}

int main(){
    int N,M,i,j,ans;
    while(scanf("%d%d",&N,&M)!=EOF&&(N||M)){
        cnt=0;
        memset(used,0,sizeof(used));
        for(i=1;i<=M;i++){
            scanf("%s",str);
            solve(N);
        }
        initmap(N);
        n=m=1<<(N);
        ans=0;
        memset(linkk,-1,sizeof(linkk));
        for(i=0;i<cnt;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
        }
        printf("%d\n",cnt-ans);
    }
    return 0;
}