题解：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

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