题意:
给一堆二进制表示的数字,如果二进制表示中有 ”*“ 则可通配0和1,比如01* 表示010和011,现在问最少能用多少个可带 ”*“的二进制新串把给的二进制原串都覆盖。
思路:
把每个原串看做点,按若两串之间不同位数小于1则有一条边建图,注意这样建图是不会有环的。然后用匈牙利算法解无向图的最小路径覆盖即可,因为是无向图,最后结果是cnt-M/2而不是cnt-M。需要注意的还有题目给原串会重。
//poj 2724 by sepNINE
#include<iostream>
using namespace std;
const int maxN=1024;
char operation[maxN][16];
bool g[maxN][maxN];
bool vis[maxN];
int link[maxN];
int flag[maxN];
int v1,v2,M;
int n,m;
int toNum(char *a)
{int x=0;for(int i=0;i<n;++i)x=x*2+(a[i]-'0');return x;
}
bool dfs(int x)
{for(int y=1;y<=v2;++y) if(g[x][y]&&!vis[y]){vis[y]=true;if(link[y]==0||dfs(link[y])){link[y]=x;return true;}}return false;
}void hungary()
{for(int x=1;x<=v1;++x){memset(vis,false,sizeof(vis));if(dfs(x))++M;} return ;
}bool codeal(int i,int j)
{int p,num=0;for(p=0;p<n;++p){if(operation[i][p]!=operation[j][p])++num;if(num>1) return false;}return true;
}int main()
{while(scanf("%d%d",&n,&m)==2){if(n==0&&m==0)break; memset(g,false,sizeof(g));memset(link,0,sizeof(link));memset(flag,0,sizeof(flag));int i,j,cnt=0;char tmp[16];for(i=1;i<=m;++i){scanf("%s",tmp);char* ptr;int x;ptr=strchr(tmp,'*');if(ptr){*ptr='0';x=toNum(tmp);if(flag[x]==0){flag[x]=1; strcpy(operation[++cnt],tmp);} *ptr='1';x=toNum(tmp);if(flag[x]==0){flag[x]=1; strcpy(operation[++cnt],tmp);} }else{x=toNum(tmp);if(flag[x]==0){flag[x]=1; strcpy(operation[++cnt],tmp);} }} for(i=1;i<=cnt;++i)for(j=i+1;j<=cnt;++j)if(codeal(i,j))g[i][j]=g[j][i]=true;v1=v2=cnt; M=0;hungary();printf("%d\n",cnt-M/2);}return 0;
}