题解：P11409 西湖有雅座

简单的图论题。

~~赛时竟然一发过了，难以置信。~~

题目分析

注意到题目中有这个条件：当

f(i,j)\ge\lceil\frac{\min(S(i),S(j))}{2}\rceil

时，

i

，

j

可以放在一起。对于这样的二元关系，很容易想到用图论建模。

先尝试将所有可以放在一起的对连边。由于一座楼要成功搭建需要其中的任意不相同点对之间有边，所以我们需要将这个图划分成两个完全图（其中一个可以为空），答案就是较大的那一半的点数。

但很多和完全图有关的问题都是较难做的。因此我们需要进一步转化。注意到我们要将原图划分成两个完全图，所以可以联想到将它转化成二分图（好吧其实应该是个板子）。原图和二分图肯定没啥关系，于是尝试建补图。通过手模可以发现，如果补图是二分图，那么就原图可以划分成两个完全图。下面略微证明一下：

假设补图不是二分图，那么一定存在奇环。奇环的最小长度为

3

，因此奇环上的任意三个点在原图上都没有边，所以这三个点只能被划分在三个完全图中。故原命题成立。

那接下来只需判断补图是否是二分图了。这就非常简单了，直接二分图染色就行了（赠送板子题链接）。然后对于二分图的每个连通块，取两个颜色中最多的加到答案里。

然后就做完了。

建图时间复杂度

O(n^2hw)

，染色复杂度

O(n)

。总的时间复杂度为

O(n^2hw)

。

AC Code

CPP

// by wangyizhi(571247)
// link: https://www.luogu.com.cn/record/194622542
// 不要试图直接复制哦！
#include<iostream>
#include<vector>
using namespace std;
int a[1001][18][18],s[1001];
vector<int> g[1001];
int c[1001],to[1001],k[1001][3];
void dfs(int u,int st)
{
	to[u]=st,k[st][c[u]]++; // 统计在 st 的这个连通块中的两种颜色的数量
	for(int v:g[u])
	{
		if(c[v]==c[u]) // 如果相邻两点被染了相同的颜色，则有奇环，不成立
		{
			cout<<-1;
			exit(0);
		}
		if(to[v]) continue;
		c[v]=3-c[u]; // 相邻两点颜色不相同 1->2 2->1
		dfs(v,st);
	}
}
int main()
{
	int n,h,w;
	cin>>n>>h>>w;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=h;j++)
			for(int k=1;k<=w;k++)
			{
				char c;
				cin>>c;
				a[i][j][k]=c-'0',s[i]+=a[i][j][k];
			}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) if(i!=j)
		{
			int cnt=0;
			for(int x=1;x<=h;x++)
				for(int y=1;y<=w;y++)
					cnt+=(a[i][x][y]&a[j][x][y]);
			if(cnt<(min(s[i],s[j])+1)/2) // 建图：对不满足条件的点对连边
				g[i].push_back(j);
		}
	for(int i=1;i<=n;i++) if(!to[i]) c[i]=1,dfs(i,i); // 如果没染色过就从这开始染
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=max(k[i][1],k[i][2]); // 取较大的加进去
	cout<<ans;
	return 11;
}

题解：P11409 西湖有雅座

文章操作

题目分析

AC Code

相关推荐

评论

题解：P11409 西湖有雅座