题解：UVA1663 净化器 Purifying Machine

UVA1663 净化器 Purifying Machine

题目意思

给你

n

个字符串，每个字符串的长度为

m

，每个字符串至多有

1

个 ∗，∗ 代表这个字符可能是

0/1

，让你构造一个字符串集合

V

（集合内每个字符串至多有一位为 ∗），使得集合内的字符串可以表示出这

V

个字符串，要求集合长度最小，输出该长度。

解题思路

我们先把这

n

字符串展开，然后暴力两两判断，如果字符串

i

跟字符串

j

只差一个字符，那么将它们连边，最后做匈牙利，得到最大匹配数，用总字符串数减最大匹配数便可。

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

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

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

因为我们发现：

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

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

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

这个图会有环吗？

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

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

CPP

#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;
}

题解：UVA1663 净化器 Purifying Machine

文章操作

UVA1663 净化器 Purifying Machine

题目意思

解题思路

相关推荐

评论

题解：UVA1663 净化器 Purifying Machine