POJ2724：Purifying Machine—

http://poj.org/problem?id=2724

描述
迈克是奶酪工厂的老板。他有2^N个奶酪，每个奶酪都有一个00 ... 0到11 ... 1的二进制数。为了防止他的奶酪免受病毒侵袭，他用一台净化机器来清理感染病毒的奶酪。净化机有N个开关，每个开关有三个状态，1,0和*。一次操作中，最多可用*一次，它可以代替1或0.当机器转到一个特定的状态时，操作将清除所有相应的二进制数字的奶酪。

有一天，迈克的机器被感染了。当麦克发现时，他已经做了一些操作，这台受感染机器操作的奶酪也被感染了。他尽可能快地清洗机器，现在他需要用最少的操作次数来清理被感染的奶酪。如果奶酪被感染，用机器清洗这个奶酪一次或多次将使这种奶酪再次免于病毒;但是如果一个奶酪没有被感染，这个奶酪的操作会使它变坏。

现在已知Mike已经完成的感染操作，你需要找出清理所有受感染的奶酪所需执行的最少操作次数。

输入
有几个测试用例。每个测试用例都包含两个数字N和M（1 <= N <= 10,1 <= M <= 1000）的行开始。以下M行中的每一行都包含机器的开关状态。 N = M = 0的测试用例结束输入，不应该被处理。

输出
对于每个测试用例，输出一行包含一个整数，这是Mike需要做的最小操作数。

示例输入

3 3
* 01
100
011
0 0

示例输出

————————————————————

因为题面很麻烦所以谷歌+手动翻译了一下。

首先将原串展开判重离散化，然后二分图最小边覆盖即可。

注意边是双向边所以用一种简单的方法解决最小边覆盖。

我们不拆点，而是连两条边（例如i到j有一条边，则A集合i连B集合j且B集合i连A集合j）

最后匹配数/2即可。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<iostream>

#include<map>

using namespace std;

const int maxn=;

map<int,bool>mp;

int t[maxn],cnt=,m,n;

bool vis[maxn],a[maxn][maxn]={};

int shu[maxn]={};

char s[];

bool dfs(int i){

    for(int j=;j<=cnt;j++){

        if(a[i][j]&&!vis[j]){

            vis[j]=;

            if(!shu[j]||dfs(shu[j])){

                shu[j]=i;

                return ;

            }

        }

    }

    return ;

}

void read(){

    cin>>s;

    int sum=;

    for(int i=;i<n;i++){

    if(s[i]=='*')sum=sum*+;

    else sum=sum*+s[i]-'';

    }

    if(!mp[sum]){

    cnt++;mp[sum]=;t[cnt]=sum;

    }

    sum=;

    for(int i=;i<n;i++){

    if(s[i]=='*')sum=sum*+;

    else sum=sum*+s[i]-'';

    }

    if(!mp[sum]){

    cnt++;mp[sum]=;t[cnt]=sum;

    }

    return;

}

int main(){

    while(cin>>n>>m){

    if(n==&&m==)break;

    memset(a,,sizeof(a));

    mp.clear();cnt=;

    for(int i=;i<=m;i++)read();

    for(int i=;i<=cnt;i++){

        for(int j=i+;j<=cnt;j++){

        int k=t[i]^t[j];

        if(k&&(k&(k-))==)a[i][j]=a[j][i]=;

        }

    }

    int ans=;

    memset(shu,,sizeof(shu));

    for(int i=;i<=cnt;i++){

        memset(vis,,sizeof(vis));

        if(dfs(i))ans++;

    }

    printf("%d\n",cnt-ans/);

    }

    return ;

}

巴特西

POJ2724：Purifying Machine——题解

最新文章

热门文章