首页 > 代码库 > poj 2724 Purifying Machine（二分图最大匹配）
poj 2724 Purifying Machine（二分图最大匹配）
题意：
有2^N块奶酪，编号为00...0到11..1。
有一台机器，有N个开关。每个开关可以置0或置1，或者置*。但是规定N个开关中最多只能有一个开关置*。
一旦打开机器的开关，机器将根据N个开关的状态对状态对应的编号的奶酪进行消毒。
例如：111 --> 对编号111的奶酪进行消毒。 说明：*代表0或1。 例如：1*1 --> 对编号为101和111的奶酪进行消毒。
现在有一些奶酪被污染了。给出这些奶酷的编号。
问最少需要几次对机器进行设定，使得所有的奶酪都被消毒。
思路：
一个带*的状态可以对两块奶酪进行杀毒。如果两块奶酪都没被之前的操作消过毒，那么这个状态是可以减少机器操作数的。所以这个带*的状态一定要操作的。
则我们要尽量地多找带*的状态，每一种状态消毒的两块奶酪都没有被其它带*的操作消过毒。二分图模型若隐若现了。
要消毒的奶酷复制一份，左边一份，右边一份，如果左边集合的某块奶酪编号和右边集合的某块奶酪编号差一位，则它们可以通过一次操作进行消毒。
求二分图的最大匹配M。
答案： 要消毒的奶酪块数 - M/2
*（未解决）：有一个东西不知道咋证。就是这个最大匹配为啥一定就是2倍的关系。
可不可能存在：假设（1-2,3 2-1,3 3-1,2） （1-2,3,4 2-1,3,4 3-1,2,4 4-1,2,3）
1-2 2-3 3-1 这样的情况。（正确应该是1-2 2-1） 或者 1-2 2-3 3-4 4-1 （虽然可以调整为1-2 2-1 3-4 4-3）
代码：
int n,m,c;char s[15];bool ex[2005];int num[2005];vector<int> graph[2005];bool bmask[2005];int cx[2005],cy[2005];int findPath(int u){ int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(!bmask[v]){ bmask[v]=true; if(cy[v]==-1||findPath(cy[v])){ cy[v]=u; cx[u]=v; return 1; } } } return 0;}int MaxMatch(){ int ans=0; rep(i,1,c) cx[i]=cy[i]=-1; rep(i,1,c) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}bool OneDigit(int x,int y){ int f=0; while(x||y){ f+=((x&1)!=(y&1)); x>>=1, y>>=1; } if(f==1) return true; else return false;}int main(){ while(scanf("%d%d",&n,&m)!=EOF,n||m){ mem(ex,false); c=0; rep(i,1,2*m) graph[i].clear(); rep(i,1,m){ scanf("%s",s); int ts1=0,ts2=0; rep(j,0,n-1){ ts1*=2; ts2*=2; if(s[j]!=‘*‘) ts1+=(s[j]-‘0‘), ts2+=(s[j]-‘0‘); else ts1+=0, ts2+=1; } if(!ex[ts1]) { num[++c]=ts1; ex[ts1]=true; } if(!ex[ts2]) { num[++c]=ts2; ex[ts2]=true; } } rep(i,1,c) rep(j,1,c){ if(OneDigit(num[i],num[j])) graph[i].push_back(j); } int dd=MaxMatch()/2; printf("%d\n",c-dd); }}
poj 2724 Purifying Machine（二分图最大匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。