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（二分图最大匹配）

最新文章

热门文章