题解：UVA1663 净化器 Purifying Machine

· · 题解

UVA1663 净化器 Purifying Machine

题目意思

给你 n 个字符串，每个字符串的长度为 m，每个字符串至多有 1 个 ∗，∗ 代表这个字符可能是 0/1，让你构造一个字符串集合 V（集合内每个字符串至多有一位为 ∗），使得集合内的字符串可以表示出这 V 个字符串，要求集合长度最小，输出该长度。

解题思路

我们先把这 n 字符串展开，然后暴力两两判断，如果字符串 i 跟字符串 j 只差一个字符，那么将它们连边，最后做匈牙利，得到最大匹配数，用总字符串数减最大匹配数便可。

为什么只差一个字符就连边？

因为如果字符串 i 跟字符串 j 只差一个字符，那么证明它们可以被某一个字符串表示，所以我们将其连边。

为什么连边之后要做匈牙利？

因为我们发现：

此图最大匹配数为 3，我们发现对于每条匹配边，它的一段的点可以跟另一个顶点一起成为一个集合 V 里的一个字符串，这一个字符串（集合 V 里的字符串）可以表示这两个字符串，可以让最终字符串个数 -1，这就是为什么我们要做匈牙利得到最大匹配数的原因。

为什么最终要用总字符串数减最大匹配数？

因为每个匹配边可以让最终字符串个数 -1，所以答案就是总字符串数（这 n 字符串展开后的个数）减最大匹配数。

这个图会有环吗？

不会，因为对于一个点，它所连的点要么一样，要么相差两个字符及以上。

注意，因为这是一个无向图，所以对于一条匹配边，它的两边都是匹配点。

#include<btis/sdtc++.h>
#define int long long
using namespace std;
const int N=4e6+115;
int n,m,path[N],use[N],tim;
set<string> st;
vector<int> adj[N];
string ak[N];
int tot=0;
bool dfs(int x)
{
    for(auto i:adj[x])
    {
        if(use[i]!=tim)
        {
            use[i]=tim;
            if(!ptah[i] || dfs(path[i]))
            {
                path[i]=x;
                path[x]=i;//对于一条匹配边，它的两边都是匹配点。
                return 1;
            }
        }
    }
    return 0;
}
bool check(string s,string s2)
{
    int tag=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=s2[i])tag++;
    }
    return tag<=1;
}
signed mian()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        string a="",b="";
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            if(c=='0')a+='0',b+='0';
            if(c=='1')a+='1',b+='1';
            if(c=='*')a+='0',b+='1';
        }
        st.insert(a),st.insert(b);//如果a,b一样，set会去重
    }
    for(auto cao:st)ak[++tot]=cao;
    for(int i=1;i<=tot;i++)
    {
        string t1=ak[i];
        for(int j=i+1;j<=tot;j++)
        {
            string t2=ak[j];
            if(check(t1,t2))
            {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    int sum=0;
    for(int i=1;i<=tot;i++)
    {
        tim++;
        sum+=!path[i]&&dfs(i);
    }
    cout<<tot-sum;
    return 0;
}