http://poj.org/problem?id=2724
#include <memory.h>
#include <stdio.h>
#include <string.h>
#define null 0
const int size = 2010;
bool e[size][size];
int maxmatch( int n, int m, bool w[][size], int *p)
{
int p_n[size];
int p_m[size];
bool sign[size];
int q[size],from[size],s,t;
int i,j,link,now,h;
memset( p_n, -1, sizeof(int)*n );
memset( p_m, -1, sizeof(int)*m );
for(i=0;i<n;i++)
if(p_n[i]==-1)
{
memset( sign, 0, sizeof(bool)*m );
s=1;link=-1;
from[0]=-1;
q[0]=size-1;
p_m[size-1]=i;
for(t=0;t<s;t++)
{
now=q[t];
for(j=0;j<m;j++)
{
if( w[p_m[now]][j] != null && sign[j]==0 )
{
sign[j]=1;
q[s]=j;
from[s++]=t;
if(p_m[j]==-1)
{
link=s-1;
break;
}
}
}
if(j<m)break;
}
if(t<s)
{
while(from[link]!=-1)
{
h=from[link];
p_m[q[link]]=p_m[q[h]];
p_n[p_m[q[h]]]=q[link];
link=h;
}
}
}
int an;
for(i=0,an=0;i<n;i++)
{
if(p)p[i]=p_n[i];
if(p_n[i]>=0)an++;
}
return an;
}
char s[2010][11];
int check( char *a, char *b ) {
int i;
for( i=0; a[i] && a[i] == b[i]; i++ )
;
if( !a[i] )
return 2;
for( i++; a[i] && a[i] == b[i]; i++ )
;
return !a[i];
}
int h;
void add( char *w, int key ) {
int k;
for( k=0; k<h; k++ )
if( check( s[k], w ) == 2 )
return;
for( k=0; k<h; k++ )
if( check( s[k], w ) ) {
if( key )
e[k][h] = 1;
else
e[h][k] = 1;
}
if( k == h )
strcpy( s[h++], w );
}
int main() {
int n, m, i, k, c;
char *cp;
char w[11];
while( scanf("%d%d", &m, &n ) == 2 && n >0 && m > 0 ) {
h = 0;
memset( e, 0, sizeof e );
for( i=0; i<n; i++ ) {
scanf( "%s", w );
c = 0;
for( k=0; w[k]; k++ )
if( w[k]=='1' )
c++;
cp = strchr( w, '*' );
if( cp ) {
*cp = '0';
add( w, c%2 );
*cp = '1';
add( w, (c+1)%2 );
}
else {
add( w, c%2 );
}
}
printf( "%dn", h-maxmatch( h, h, e, 0 ) );
}
return 0;
}