【poj2724】 Purifying Machine
http://poj.org/problem?id=2724 (题目链接)
题意
Mike有一个机器可以帮助他清理奶酪，每个奶酪由一个n位二进制数表示，机器上一共有n个按钮，每个按钮有1，0，＊，其中‘＊’表示既可以是1也可以是0。每次操作都可以命令机器生成一个二进制数。因此机器可以表示出一个或两个二进制数，这样就可以清理奶酪了。现在问要清理m块n位的二进制奶酪需要操作多少次。
Solution
如果两个奶酪只有一位不同，那么就可以通过一次操作将两个都消掉，这样的奶酪当然是越多越好，因此，很容易就想到了二分图匹配求最小路径覆盖。如果两个奶酪的二进制数只有一位不同，就将这两个连边。所以先去重，再连边，连完边后跑匈牙利就可以了。
刚开始用string写的，结果莫名其妙的Wa，调试还看不到，改成char就A了，可惜代码丑了许多。
代码
// poj2724
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
int f,x=0;char ch=getchar();
while (ch<='0' || ch>'9') {if (ch=='-') f=-1;else f=1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=10010;
struct edge {int to,next;}e[maxn<<2];
int n,m,head[maxn],vis[maxn],p[maxn],cnt;
//string s[maxn];
char s[maxn][10];
bool cmp(int x,int y) {
int tot=0;
for (int i=0;i<n;i++)
if (s[x][i]!=s[y][i]) {tot++;if (tot>1) return 0;}
return 1;
}
void insert(int u,int v) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
bool find(int x) {
for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) {
vis[e[i].to]=1;
if (p[e[i].to]==0 || find(p[e[i].to])) {
p[e[i].to]=x;
return 1;
}
}
return 0;
}
void check(int x) {
for (int i=0;i<n;i++) if (s[x][i]=='*') {
s[x][i]='1';m++;
for (int j=0;j<n;j++) s[m][j]=s[x][j];
s[m][i]='0';
}
}
int main() {
int M;
while (scanf("%d%d",&n,&M)!=EOF && n && M) {
m=0;cnt=0;
for (int i=1;i<=M;i++) {
m++;
cin>>s[m];
check(m);
}
int x=0;
for (int i=1;i<=m;i++) {
int flag=0;
for (int j=1;j<=x;j++) {
flag=1;
for (int k=0;k<n;k++) if (s[i][k]!=s[j][k]) {flag=0;break;}
if (flag) break;
}
if (!flag) memcpy(s[++x],s[i],sizeof(s[i]));
}
m=x;
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
if (i!=j && cmp(i,j)) insert(i,j);
int ans=0;
for (int i=1;i<=m;i++) {
for (int j=1;j<=m;j++) vis[j]=0;
if (find(i)) ans++;
}
printf("%d
",m-ans/2);
for (int i=1;i<=m;i++) p[i]=head[i]=0;
}
return 0;
}