[agc006F]Blackout

Description

传送门

Solution

这道题的操作是真的得服气。。感谢各位大佬的指导。

首先我们看看答案的最大值:10¹⁰。哦不，这不可能存在，我们肯定不可能一轮轮枚举点进行扩展的。

所以，接下来我们进入正题：

由于我们不可能计算出所有具体的点，我们肯定得依靠某种玄学秘法来表示原本的点（不然你没法往下推啊qaq），然后通过神秘手段来搞事情。

em我们把一个点(x,y)看做是一条x->y的有向边。如果有x->y,y->z,则我们可以加上边z->x。

这些点将构成若干联通块，我们对其进行染色。

我们一共染3种色0,1,2。如果有x->y，则y的颜色为(x的颜色+1)%3。

对于某个联通块，有3种情况。

1，一共只用了两种颜色并且没有一个点被染了两种色，我们可以形象地理解为该图只有两层，但是我们需要3层才可以额外加边，答案不变。

2，一共刚好用了3色并且没有一个点被染了两种色，则2色的可以连向0色，0色的可以连向1色，1色的可以连向2色，统计加了多少边就好。

3，有一个点被染了两种色，图中出现环。环中任意两点x,y将会存在x->y,y->x。然后可证明，这时如果往这个环外多加一个点，在操作完成后也会满足任意两点x,y有x->y,y->x。即该联通块的边总数为点数的平方。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int n,m,x,y;

struct node{int y,nxt,t;

}g[];int h[],tot=;

int cnt[],col[],_point,_link;

bool vis[],_is;

void dfs(int x)

{

    cnt[col[x]]++;vis[x]=;_point++;

    for(int i=h[x];i;i=g[i].nxt)

    {

        _link+=(g[i].t==);

        if (!vis[g[i].y]) col[g[i].y]=(col[x]+g[i].t+)%,dfs(g[i].y);

        else if (col[g[i].y]!=(col[x]+g[i].t+)%) _is=;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=m;i++)

    {

        scanf("%d%d",&x,&y);

        g[++tot]=node{y,h[x],};h[x]=tot;

        g[++tot]=node{x,h[y],-};h[y]=tot;

    }

    long long ans=;

    for (int i=;i<=n;i++)

    {

        if (vis[i]) continue;

        _is=;_point=_link=;cnt[]=cnt[]=cnt[]=;

        dfs(i);

        if (!_is) ans+=1ll*_point*_point;

        else if (cnt[]&&cnt[]&&cnt[]) ans+=1ll*cnt[]*cnt[]+1ll*cnt[]*cnt[]+1ll*cnt[]*cnt[];

        else ans+=_link;

    }

    printf("%lld",ans);

}

巴特西

[agc006F]Blackout

Description

Solution

Code

最新文章

热门文章