Purifying Machine
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 4026 | Accepted: 1132 |
Description
Mike is the owner of a cheese factory. He has 2N cheeses and each cheese is given a binary number from 00...0 to 11...1. To keep his cheese free from viruses, he made himself a purifying machine to clean virus-infected cheese. As a talented programmer, his purifying machine is built in a special way. His purifying machine has N switches, each switch has three states, 1, 0 and *. An operation of this machine is a cleaning action according to the states of the N switches. During one operation, at most one switch can be turned to state *, which can substitute for either 1 or 0. When the machine is turned to a specific state, an operation will clean all the cheeses with corresponding binary numbers. For example, if N equals 6 and the switches are turned to 01*100, the cheeses numbered 010100 and 011100 are under operation by the machine.
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.
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
There 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
For each test case, output one line containing an integer, which is the minimum number of operations Mike needs to do.
Sample Input
3 3 *01 100 011 0 0
Sample Output
2
题意:
给出 N(1 ~ 10),M(1 ~ 1000),代表每个按钮有 N 个键,每个键都有 3 种状态分别是 0 ,1, *。* 可以代替0或者1。后给出 M 个被感染的按钮,问如何操作这些按钮使感染的按钮不被感染。输出这个最小操作数。若给出样例,给出感染的数是*01,100,011,有*,说明有4个数被感染:001,101,100,011。故选择 10* 和 0*1 这两个操作。故最少操作为2。
思路:
二分图的最大匹配。将所有被感染的数都化开,变成不带*的状态,后要去重,因为可能会有重复的数。若不考虑匹配的时候,每个数都代表一个操作,每增加一个 * 就能减少一个操作,那么可以用二分图来解决问题。建图关系为两个数间相差一个数。后总共的数 - 最大匹配即可得出结果。化成二进制标记来判重。
AC:
#include <cstdio> #include <algorithm> #include <string.h> using namespace std; int n,m,ans; int w[2005][2005],linker[2005],vis[2005]; int temp[2500]; int test2(char *a) { int res = 0,k = 1; for(int i = n - 1;i >= 0;i--) { res += k * (a[i] - '0'); k *= 2; } return res; } int test(char *a,char *b) { int sum = 0; for(int i = 0;i < n;i++) { if(a[i] != b[i]) sum++; if(sum >= 2) return 0; } return 1; } bool dfs(int u) { for(int v = 0;v < ans;v++) if(w[u][v] && !vis[v]) { vis[v] = 1; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int u = 0;u < ans;u++) { memset(vis,0,sizeof(vis)); if(dfs(u)) res++; } return res; } int main() { char s[2005][15]; while(~scanf("%d%d",&n,&m) && (n + m)) { memset(temp,0,sizeof(temp)); memset(w,0,sizeof(w)); ans = 0; while(m--) { char str[15]; int pos = -1; scanf("%s",str); for(int i = 0;i < n;i++) if(str[i] == '*') { pos = i; break; } int res; if(pos != -1) { str[pos] = '1'; res = test2(str); if(!temp[res]) { strcpy(s[ans++],str); temp[res] = 1; } str[pos] = '0'; res = test2(str); if(!temp[res]) { strcpy(s[ans++],str); temp[res] = 1; } } else { res = test2(str); if(!temp[res]) { strcpy(s[ans++],str); temp[res] = 1; } } } for(int i = 0;i < ans - 1;i++) for(int j = i + 1;j < ans;j++) if(test(s[i],s[j])) { w[i][j] = 1; w[j][i] = 1; } printf("%d\n",ans - hungary() / 2); } return 0; }
相关推荐
真核表达纯化APP蛋白胞外端用于研究其信号转导机制,陈克平,窦非,AD主要病理特征是脑部神经斑块与神经纤维缠结的密度及分布的病理变化,而目前对参与神经斑块形成的前体蛋白APP的正常功能了解甚少�
The influence of optical breakdown on stimulated Brillouin scattering (SBS) process is investigated with purified CCl4, acetone, and CS2 mediums which are obtained through 0.22-μm pore-size filter....
实现人ReID的高效数据生成 ...├── data-purifying-GCN # training and testing code for data purifying │ └── feature-extraction # extract features for affinity graph construction │
Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....1. Introduction....2. First-Class Functions....3. Pure Functions....Purifying Our Functions 29 iii
5 Cleaning and Purifying 109 5.1 Pure Fun 109 5.2 Conventional Purifi cation Methods 113 5.2.1 The Column Technique 113 5.2.2 Purifi cation Based on Size Differences 114 5.2.3 Purifi cation Based on ...
OLGenie:估计重叠基因(OLG)中的dNdS的程序