洛谷[AT_agc006_f]Blackout题解

题目

难度：本题目前难度为 NOI/NOI+/CTSC

原题链接

题目描述

我们有一个 N 行 N 列的矩阵。第 i 行第 j 列的格子表示为 (i,j)。

开始时，有 M 个格子是黑色，其他格子都是白色。特别地，开始时格子 (a[1],b[1]),(a[2]​,b[2]​),…,(a[M],b[M]) 是黑色。

スヌケ君会按照以下的规则尽可能多的将白色格子涂成黑色：

对于整数 1≤x,y,z≤N，如果 (x,y) 和 (y,z) 都是黑色，那么就把 (z,x) 涂黑。

请计算出当再也没有白色格子能被涂黑时，黑色格子的个数。

变量范围及条件

• 1≤N≤105

• 1≤M≤1051≤M≤105

• 1≤ai,bi≤N1≤ai​,bi​≤N

• 各黑格坐标互不相同

输入格式

从标准输入输入，格式见下：

第一行包含两个整数 N 和 M；

从第二行开始的 M 行，每行有两个以空格隔开的整数 a[i] ​和 b[i]​，表示第 i 个黑色格子的坐标。

输出格式

输出一个整数到标准输出，表示当尽可能多的把格子涂黑之后，黑色格子的个数。

输入输出样例

输入 #1

3 2
1 2
2 3

输出 #1

3

输入 #2

2 2
1 1
1 2

输出 #2

4

输入 #3

4 3
1 2
1 3
4 4

输出 #3

3

样例解释

#1

可以按这样的方法涂黑一个格子：

• 因为格子(1,2)(1,2)和(2,3)(2,3)都是黑色而(3,1)(3,1)是白色，把(3,1)(3,1)涂黑。

#2

可以按这样的方法涂黑两个格子：

• 因为格子(1,1)(1,1)和(1,2)(1,2)都是黑色而(2,1)(2,1)是白色，把(2,1)(2,1)涂黑。

• 因为格子(2,1)(2,1)和(1,2)(1,2)都是黑色而(2,2)(2,2)是白色，把(2,2)(2,2)涂黑。

#3

很遗憾，没有任何白色格子能被涂黑。

思路

这道题我们直接进行暴力枚举是不现实的，因为它是黑题。 我们光看存储这个矩阵就能知道，需要 1e5*1e5 的矩阵，也就是 1e10。这样的矩阵用 bool 类型存都是不可行的。再说时间复杂度，纯暴力的时间复杂度可达 O(n^3)，1e5 的数据范围显然是行不通的。

所以，我们可以把它当做一个三色图来存（分别指 (x,y),(y,z),(z,x) 三个位置）。

三色图的是一种特殊的有向图，每一个节点都含有一个颜色。而它的染色标准可以理解为：红色的下一个节点是绿色，绿色的下一个节点是蓝色，蓝色的下一个节点又是红色。

虽然是有向图，但是我们需要知道上一个节点的颜色和下一个节点的颜色，所以，我们可以用带权的无向图来存储，正向的边权值是 1，反向是 -1，这样我们可以直接通过加上通过的边的权值来找到下一个或上一个节点的颜色。

不过，节点的颜色是循环的，例如蓝色 (2 号色) 的下一个颜色是红色 (0 号色)，而单纯地加上所通过的边的权值 “1” 会变成 3 号色，这是不被允许的，所以，我们还需要一个函数，来修正颜色的值，如下：

inline int col(int colour)
{
    if(colour>=3)colour-=3;
    if(colour<0)colour+=3;
    return colour;
}

这时候，我们对于从每个节点 i (1<=i<=n) 出发的边，需要求出联通块的大小，这一步可以通过 dfs 解决。如果染色失败，那么对答案的贡献为走过的点的个数的平方。如果在联通块中所有颜色都出现过了，对答案的贡献则是
( 红色点个数 * 绿色点个数 + 绿色点个数 * 蓝色点个数 + 蓝色点个数 * 红色点个数 )。

如果以上条件皆不满足，则对答案的贡献是走过的正向边的个数。

完整代码

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

int n,m;
int h[100005],to[200005],ne[200005],w[200005],idx; //链式前向星存图
int color[200005],colorsum[5],n1,m1;
bool flag,vis[200005];
int sum;

inline void AddEdge(int u,int v,int x) //新增边
{
    to[idx]=v;
    w[idx]=x;
    ne[idx]=h[u];
    h[u]=idx++;
}

inline int col(int colour) //修正颜色编号函数
{
    if(colour>=3)colour-=3;
    if(colour<0)colour+=3;
    return colour;
}

inline void colored(int x) //DFS求联通块
{
    colorsum[color[x]]++;
    n1++;
    vis[x]=true;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int y=to[i];
        if(w[i]==1)m1++;
        if(!vis[y])
        {
            color[y]=(col(color[x]+w[i]));
            colored(y);
        }
        else if(color[y]!=(col(color[x]+w[i])))
        {
            flag=true;
        }
    }
}

signed main(void)
{
    memset(h,-1,sizeof(h));
    scanf("%lld%lld",&n,&m);
    
    while(m--)
    {
        int u,v;
        scanf("%lld%lld",&u,&v);
        AddEdge(u,v,1);
        AddEdge(v,u,-1);
    }
    
    for(int i=1;i<=n;i++) //对于每个点，从这个点出发的联通块和贡献计算
    {
        if(vis[i])continue;
        memset(colorsum,0,sizeof(colorsum));
        n1=0;
        m1=0;
        flag=false;
        colored(i);
        if(flag)sum+=n1*n1;
        else if(colorsum[0]&&colorsum[1]&&colorsum[2])
        {
            sum+=(colorsum[0]*colorsum[1]+colorsum[1]*colorsum[2]+colorsum[2]*colorsum[0]);
        }
        else sum+=m1;
    }
    printf("%lld",sum); //输出答案
    return 0;
}

于是，本题至此 AC。

---