题解 AT2167 【Blackout】

· · 题解

2024.07.21 update. 更新了本题结论的证明。

题意

你有一个 N\times N 的网格，一开始有 M 个格子是黑色的。

如果格子 (x,y) 和 (y,z) 都是黑色的，那你可以把 (z,x) 也给涂黑

问最多能有多少个黑格子

题解

问题转化一下：你有一个 N 个点的有向图，一开始连了 M 条边，假如存在边 x\to y 和 y\to z，那么你可以连边 z\to x。这样就可做多了。

我们考虑对原图进行三染色。假设某一个点是红，他连向的所有点就是蓝；蓝连向的所有点都是绿；绿连向的所有点又是红。

假如我们对某个弱连通块染色失败，那么这个弱连通块会被操作成一个完全图（见下方证明），那么这种染色失败的弱连通块对答案的贡献就是 n\times n（n 表示弱连通块内点的数量）

假如染色成功，但是只存在一种或两种颜色，那么这个弱连通块分成了两层，并且只存在上层指向下层的边。这种情况下根本无法进行操作，所以对答案的贡献就是弱连通块的初始边数

假如染色成功，并且三种颜色都存在，那么在若干次操作之后，任意一个红点都会有直接连向所有蓝点的出边，类似的，蓝连向绿，绿连向红。这种情况称为 “全连接”（见下方证明）。所以这种情况对答案的贡献就是 cnt_r\times cnt_b+cnt_b\times cnt_g+cnt_g\times cnt_r， 其中 cnt_x 表示颜色为 x 的点在弱连通块里有多少个，r,g,b 是颜色缩写

就这样直接做就行了，代码实现非常简单，ans记得要开 long long

#include<bits/stdc++.h>
using namespace std;

const int S=(1<<20)+5;
char buf[S],*H,*T;
inline char Get()
{
    if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
    if(H==T) return -1;return *H++;
}
inline int read()
{
    int x=0;char c=Get();
    while(!isdigit(c)) c=Get();
    while(isdigit(c)) x=x*10+c-'0',c=Get();
    return x;
}

const int N=200010;
struct Edge{int to,capa,next;} e[N];
int h[N],sum=0,n,m;
bool vis[N];
int cmt,cnt,col[N],c[3];
bool falun;

inline int color(const int &x)
{
    if(x>=3) return x-3;
    if(x<0) return x+3;
    return x;
}

void add_edge(int u,int v,int w)
{
    e[++sum].to=v;
    e[sum].capa=w;
    e[sum].next=h[u];
    h[u]=sum;
}

void dfs(int u)
{
    c[col[u]]++;vis[u]=1;cnt++;
    for(int tmp=h[u];tmp;tmp=e[tmp].next)
    {
        cmt+=(e[tmp].capa==1);
        int v=e[tmp].to;
        if(!vis[v]) col[v]=color(col[u]+e[tmp].capa),dfs(v);
        else if(col[v]!=color(col[u]+e[tmp].capa)) falun=0;
    }
}

int main()
{
    int u,v;
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        u=read();v=read();
        add_edge(u,v,1);
        add_edge(v,u,-1);
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        memset(c,0,sizeof(c));
        cmt=cnt=0;falun=1;
        dfs(i);
        if(!falun) ans+=1ll*cnt*cnt;
        else if(c[0]&&c[1]&&c[2]) ans+=1ll*c[0]*c[1]+1ll*c[1]*c[2]+1ll*c[2]*c[0];
        else ans+=cmt;
    }
    printf("%lld\n",ans);
    return 0;
}

证明路线

先依次证明以下四条性质。

性质1： 完全图具有 “感染性”。即：在一个完全图的基础上 连接任意一个点，这个点都会和原图的所有点形成双向边、以及一个自环， 从而成为更大的完全图。 所以只要一个弱连通块存在完全子图，那么它就会演化为完全图

性质2： 四元环会演化出二元完全子图，所以会被感染为完全图。

性质3： 五元环会演化出二元完全子图，所以会被感染为完全图。

性质4： 设 n\;(n\geq 7\; \text{且不是}\; 3 \; \text{的倍数}) 元环中，点的编号为 1,...,n；首先可以生成 3\to 1,\; 1\to (n-1) 两条边，这两条边又可以引出 (n-1)\to 3，此时 3,4,...,(n-1) 构成一个 (n-3) 元环。由归纳法得到：该 n 元环会演化出四元环或五元环。因此由前三条性质，它最终演化为完全图。

借助前四个性质，可以说明：染色失败时，最终会变成一个完全图。（因为染色失败必然包含一个长度不能被 3 整除的环）

性质5： 三元链可以变成三元环。

性质6： 对于成功染色且有三种颜色的情况， 如果两条三元环 r_1\to g_1\to b_1\to r_1 与 r_2\to g_2\to b_2\to r_2 之间存在初始连接， 那么它们会演化为全连接。

借助性质 5、性质 6，可以说明：对于成功染色且有三种颜色的情况，最终整个弱连通块会演变成三层全连接。（每一对三元环只要存在初始连接，就会演化成全连接，而弱连通块里三元环都是直接或间接相连的，所以最终全部演化为全连接）