题意：
会给出M个串，我们要做的就是将这M个串给清除了。对于任意两个串，若二进制形式只有一位不一样，那么这两个串可以在一次操作消除，否则每个操作只能消除一个串。
3 3
*01
100
011
可以代表的串是
001
101
100
011
那么我们可以先用 10*把 101 和 100 消除了，再用 0*1把001 和 011 消除了。故操作次数为 2。
解题思路：
我们可以将所有的串先化为整数，并去重。然后对二进制形式只有一位不一样的两个数，我们由含有偶数个1的数向含有奇数个1的数连边，这样就确保了一定是二分图，因为不存在同含奇数个1或同含偶数个1 的数只相差一位。最后进行求最大匹配，既是我们可以省去的操作数。所以我们求得最大独立集才是最终答案。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define Maxn 1200 using namespace std; int graphic[Maxn][Maxn],vi[Maxn],match[Maxn],n,m,ans[Maxn],e; int dfs(int u)//匈牙利算法 { int i; for(i=1;i<=e;i++) { if(!vi[i]&&graphic[u][i]) { vi[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } } return 0; } int main() { int i,j,k,Case=1,a,b,num1,num2,Exp[13]; char str[11]; Exp[0]=1; for(i=1;i<=12;i++) Exp[i]=Exp[i-1]*2; while(scanf("%d%d",&n,&m),n||m) { memset(match,-1,sizeof(match)); memset(graphic,0,sizeof(graphic)); memset(ans,0,sizeof(ans)); e=0; for(i=1;i<=m;i++) { scanf("%s",&str); num1=0;num2=-1; for(j=n-1;j>=0;j--) { if(str[j]!='*') num1+=Exp[n-j-1]*(str[j]-'0'); else num2=Exp[n-j-1]; } ans[++e]=num1; if(num2!=-1) ans[++e]=num1+num2; } int num=1; sort(ans+1,ans+e+1);//排完序后进行去重 for(i=2;i<=e;i++) if(ans[i]!=ans[num]) ans[++num]=ans[i]; e=num; for(i=1;i<=e;i++) { for(j=i+1;j<=e;j++) { int temp=(ans[i]^ans[j]);//找出不同位 if((temp&(temp-1))==0)//若不同位只有一位,则为0 { temp=ans[i]; num=0; while(temp)//求出二进制数1的个数 { num++; temp=temp&(temp-1); } if(num%2==0)//判断1的个数是奇数还是偶数 graphic[i][j]=1; else graphic[j][i]=1; } } } num=0; for(i=1;i<=e;i++) { memset(vi,0,sizeof(vi)); if(dfs(i)) num++; } printf("%d ",e-num); } return 0; }