POJ2724 Purifying Machine【二分图最小边覆盖】
题目链接:
http://poj.org/problem?id=2724
题目大意:
有2^N个奶酪,编号从000…00到111…11,现在有台机器有N个开关,每个开关的状态有3个,
分别是‘0‘、‘1‘、‘*‘,每个开关只能有一个状态存在。‘*‘状态可以替代‘0‘或‘1‘状态。比如11*1,
对应为1111或1101。现在有M个奶酪被感染了,每个奶酪的编号为长度为N的二进制字符串。
和开关一样,每一位上除了能为‘1‘、‘0‘之外,还可以是‘*‘,表示既能是‘0‘,也能是‘1‘。比如说
1*1,既可以是101,也可以是111。现在要把这些被感染的奶酪(二进制字符串)都删除掉。删除
的方法有两种:
1)通过和被感染的奶酪编号一样的机器一次删除指定的一个字符串,比如说用111删除111。
2)如果有两个串只有一个字符不同,则可以用带‘*‘的字符串一次性同时删除这两个字符串(其中包
括重复的串),比如说用1*1同时删除101和111。
机器每删除一次,就要转换一次状态再进行下一次删除。问:机器最少要转换多少次状态才能将
所有串删除完。
思路:
将所有的二进制串都变为只包含01的二进制串,然后用数组Num[]来存储二进制串对应的十进制
数,比如说101对应十进制就是5。然后对Num[]数组排序,删除所有重复的数。这样子,就可以
用点来表示字符串了。假设有cnt个无重复数的点(二进制串)。然后,建立二分图,每边都是cnt个
点。对于所有满足二进制形式只差一位的两个点进行双向建边。最后问题就变为了:求二分图最小
边覆盖问题。二分图最小边覆盖 = 点数cnt - 二分图最大匹配/2。用匈牙利算法求二分图最大匹配
即可。
对于判断数A和数B的二进制形式是否只差一位,可通过 t = A^B,然后判断(t && (t&(t-1))==0),
满足,则A和B的二进制形式只差一位。
AC代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 2050; bool Map[MAXN][MAXN],Mask[MAXN]; int NX,NY; int cx[MAXN],cy[MAXN]; int FindPath(int u) { for(int i = 1; i <= NY; ++i) { if(Map[u][i] && !Mask[i]) { Mask[i] = 1; if(cy[i] == -1 || FindPath(cy[i])) { cy[i] = u; cx[u] = i; return 1; } } } return 0; } int MaxMatch() { for(int i = 1; i <= NX; ++i) cx[i] = -1; for(int i = 1; i <= NY; ++i) cy[i] = -1; int res = 0; for(int i = 1; i <= NX; ++i) { if(cx[i] == -1) { for(int j = 1; j <= NY; ++j) Mask[j] = 0; res += FindPath(i); } } return res; } char s[12]; int Num[MAXN]; int main() { int N,M; while(~scanf("%d%d",&N,&M) && (N||M)) { memset(Map,0,sizeof(Map)); memset(Num,0,sizeof(Num)); int cnt = 0,k; for(int i = 1; i <= M; ++i) { scanf("%s",s); cnt++; k = -1; for(int j = 0; j < N; ++j) { if(s[j] == '*') k = j; else Num[cnt] |= ((s[j]-'0')<<j); } if(k != -1) { cnt++; Num[cnt] = (Num[cnt-1] | (1 << k)); } } sort(Num+1,Num+1+cnt); Num[0] = -1; int j = 0; for(int i = 1; i <= cnt; ++i) if(Num[j] != Num[i]) Num[++j] = Num[i]; cnt = j; for(int i = 1; i <= cnt; ++i) { for(int j = i+1; j <= cnt; ++j) { int t = Num[i]^Num[j]; if(t && (t&(t-1))==0) Map[i][j] = Map[j][i] = 1; } } NX = NY = cnt; int Max = MaxMatch(); printf("%d\n",cnt - Max/2); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。