| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 4014 | Accepted: 1127 |
Description
One day, Mike's machine was infected. When Mike found out, he had
already done some operations and the cheeses operated by this infected
machine were infected too. He cleaned his machine as quickly as he
could, and now he needs to clean the infected cheeses with the minimum
number of operations. If a cheese is infected, cleaning this cheese with
the machine one or more times will make this cheese free from virus
again; but if a cheese is not infected, operation on this cheese will
make it go bad.
Now given the infected operations Mike has done, you need to find
out the minimum number of operations that must be performed to clean all
the infected cheeses without making any clean cheese go bad.
Input
are several test cases. Each test case starts with a line containing
two numbers N and M (1 <= N <= 10, 1 <= M <= 1000). N is the
number of switches in the machine and M is the number of infected
operations Mike has done. Each of the following M lines contains a
switch state of the machine. A test case with N = M = 0 ends the input
and should not be processed.
Output
Sample Input
3 3
*01
100
011
0 0
Sample Output
2
Source
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; #define maxn 2005 int n,m,len,ans;
int ele[maxn],match[maxn];
vector<int> G[maxn];
bool vis[maxn]; bool judge(int x1,int x2) {
int sum = ;
for(int i = ; i < ; ++i) {
if((x1 >> i & ) ^ (x2 >> i & )) ++sum;
} return sum == ;
}
void build() {
for(int i = ; i < len; ++i) {
for(int j = i + ; j < len; ++j) {
if(judge(ele[i],ele[j])) {
G[i].push_back(j);
G[j].push_back(i);
}
}
} } bool dfs(int u) {
for(int i = ; i < G[u].size(); ++i ) {
int v = G[u][i];
if(vis[v]) continue;
vis[v] = ;
if(match[v] == - || dfs(match[v])) {
match[v] = u;
return true;
}
} return false;
} void solve() { for(int i = ; i < len; ++i) G[i].clear();
build(); for(int i = ; i < len; ++i) {
match[i] = -;
} for(int i = ; i < len; ++i) {
memset(vis,,sizeof(vis));
if(dfs(i)) ++ans;
}
} int main()
{
// freopen("sw.in","r",stdin);
while(~scanf("%d%d",&n,&m)) {
len = ;
ans = ;
if(!n && !m) break;
char ch[];
for(int i = ; i < m; ++i) {
scanf("%s",ch);
int pos = -,sum = ;
for(int j = ; j < n; ++j) {
if(ch[j] == '')
sum += ( << (n - j - ));
if(ch[j] == '*')
pos = n - j - ;
} ele[len++] = sum;
if(pos != -) ele[len++] = sum + ( << pos); } sort(ele,ele + len);
len = unique(ele,ele + len) - ele; solve(); printf("%d\n",len - (ans / ));
} return ;
}