poj 2724 Purifying Machine（二分图最大匹配）

浏览数：26 / 时间：2015年06月20日

题意：

有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);
    }
}