传送门:

AtCoder

洛谷


题目大意:

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

开始时,有M个格子是黑色,其他格子都是白色。特别地,开始时格子(a_{1},b_{1}),(a_{2},b_{2}), \cdots ,(a_{M},b_{M})是黑色。

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

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

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

解题思路:

首先有个(我觉得)很妙的转化:

题意其实可以转化成有N个点,开始连了M条边,如果xy有边,yz有边,那么zx就可以连边。

这个是很显然的,你把网格图第i行拎出来,上面描黑的点的列的编号实际上就是i连向的点。

然后我们显然可以考虑染色,颜色col \in [0,2],设点x颜色为0,点y颜色为1,点z颜色为2

我们现在分情况考虑其对答案的贡献:

  • 对于一个染色失败的联通块,显然最后会被整成完全图,那么其对答案的贡献就是size*size,其中size是这个联通块的大小。
  • 对于一个染色成功但颜色不全的联通块,那么贡献就是边数。
  • 对于一个染色成功且颜色齐全的联通块,其对答案的贡献就是cnt_0 \times cnt_1 +cnt_1 \times cnt_2 +cnt_2 \times cnt_0,其中cnt_i表示颜色为i的点数。

因此我们dfs染色统计就好了。

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+10;
struct node{int to,nxt,w;}e[maxn<<1];
int n,m,tot,bel,sec,flag,cnt[3],head[maxn],vis[maxn],col[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(ll x){print(x);puts("");}
void add(int u,int v,int w){e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;}
void dfs(int x){
    cnt[col[x]]++;vis[x]=1;bel++;
    for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to){
        if(e[i].w==1)sec++;
        if(!vis[v])col[v]=(col[x]+e[i].w+3)%3,dfs(v);
        else if(col[v]!=(col[x]+e[i].w+3)%3)flag=1;
    }
}
int main(){
    n=read();m=read();ll ans=0;
    for(int i=1;i<=m;i++){int u=read(),v=read();add(u,v,1);add(v,u,-1);}
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        memset(cnt,0,sizeof(cnt));
        bel=sec=flag=0;dfs(i);
        if(flag)ans+=1ll*bel*bel;
        else if(cnt[0]&&cnt[1]&&cnt[2])ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[0];
        else ans+=sec;
    }write(ans);
    return 0;
}

发表评论