[二分匹配]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;}