POJ 2724 Purifying Machine(二分图最大匹配)

POJ 2724 Purifying Machine(二分图最大匹配)

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

题意:

给出m串长度为n的01串。有些串中可能包含*，这样的串可以表示两个串，*为1 和*为0。重复的算一种。比如题目中

*01

100

011

就代表了四个01串(注意输入的串需要判断重复)

001

101

100

011

现在我们需要消灭掉所有的01串，消灭方式有两种：

1一次消灭一个串。

2如果两个串的差别只有一位的话可以同时消灭这两个串。

问最少多少次操作可以消灭所有的01串

分析:

也就是给你一些不同的(判重之后)二进制串,每个串可以通过1次操作净化,也可以把两个只有1位不同的串通过1次操作联合净化.要我们求最少的操作次数.

我们把所有串按其中1的个数和是奇还是偶分成左右两个点集.

对于任意两个串,如果他们只有1位不同,那么就在他们之间连接一条无向边.(这两个串一定分别属于不同的点集)

由于串的总数是固定的,且一个串可以通过单独净化也可以通过联合净化.而我们向让净化的次数最少,我们自然想联合净化(即一次可以净化两个串)的次数尽量多了. 那么我们最多可以进行多少次联合净化呢? 这个数值==我们建立二分图的最大匹配边数.(想想是不是,因为一个串最多只能被净化一次)

假设总的不同串有n个,我们建立二分图的最大匹配数(即联合净化最大次数)为ans,那么我们总共需要n-ans次净化即可.(想想为什么)

当然本题也可以不用把串特意分成左右点集(本程序实现就是用的这种方式),我们只需要把原图翻倍,然后求翻倍图的最大匹配数ans,最后用n-ans/2即可.(类似于POJ1466:

http://blog.csdn.net/u013480600/article/details/38638219).

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<string>
#include<iostream>
using namespace std;
const int maxn=1000+100;

struct Max_Match
{
    int n;
    vector<int> g[maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n)
    {
        this->n=n;
        for(int i=1;i<=n;i++) g[i].clear();
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                if(left[v]==-1 || match(left[v]))
                {
                    left[v]=u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ++ans;
        }
        return ans;
    }
}MM;

struct Node
{
    string s;
    bool link(Node& rhs)//判断两个string是否只相差1位
    {
        int num = 0;
        for(int i=0;i<s.size(); i++)
            if(s[i]!=(rhs.s)[i]) ++num;
        return num==1;
    }
}node[maxn];

int main()
{
    int N,M;
    while(scanf("%d%d",&N,&M)==2 && N)
    {
        int num=0;
        set<string> st;//判重string
        for(int i=1;i<=M;i++)
        {
            string s;
            cin>>s;
            if(s.find("*")!=-1)
            {
                int pos=s.find("*");
                string s1(s),s2(s);
                s1[pos]='0';
                s2[pos]='1';
                if(st.find(s1) == st.end())//s1与已有string不重复
                {
                    st.insert(s1);
                    node[++num].s = s1;
                }
                if(st.find(s2) == st.end())//s2与已有string不重复
                {
                    st.insert(s2);
                    node[++num].s = s2;
                }
            }
            else
            {
                if(st.find(s) == st.end())
                {
                    st.insert(s);
                    node[++num].s = s;
                }
            }
        }

        MM.init(num);
        for(int i=1;i<=num;i++)
        for(int j=1;j<=num;j++)if(i!=j)
        if(node[i].link(node[j]))
            MM.g[i].push_back(j);
        printf("%d\n",num-MM.solve()/2);
    }
    return 0;
}