大意:给定感染的物品(二进制)表示,一次操作可以消去一个物品,如果两个物品的二进制相差一位的话,那么可以一次消去两个,问最少多少次消去。
思路:通过最大匹配求节省的次数(ans/2),然后用点集数减去已消去的物品数加上以前的操作数ans/2即可,res = ans/2, res += nx-ans;
给出建图的代码:
int check(int a, int b) //相差一位 { int c = a^b; int num = 0; while(c) { c &= (c-1); num++; } return num == 1; } int read_case() { readint(n), readint(m); if(!n) return 0; init(); nx = 0; bool vis[maxn] = {0}; for(int i = 0; i < m; i++) { scanf("%s", STR[i]); int flag = -1; int t = 0; for(int j = 0; j < n; j++) { if(STR[i][j] == '*') { flag = j; continue; } if(STR[i][j] == '1') t += fac[j]; } if(!vis[t]) { vis[t] = 1; num[nx++] = t;} if(flag != -1 && !vis[t+fac[flag]]) { vis[t+fac[flag]] = 1; num[nx++] = t+fac[flag]; } } return 1; }