【思维题】【图论】AGC011 C——Squared Graph

72 阅读 0 评论 48 点赞

我是靠谱客的博主无心小熊猫，最近开发中收集的这篇文章主要介绍【思维题】【图论】AGC011 C——Squared Graph，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目传送门

~~考场上企图用归纳法来做,然而事实证明我依旧似乎走错了方向.~~

题目中的定义了图的乘法,然后来根据图的不同特征进行讨论.
首先我们考虑一种最简单的情况,设A,B是两个图,并且它们都是一个单点,那么A对答案的贡献为 $∣ B ∣$ .反之对B同理.

然后考虑两个图都没有奇环的情况,(似乎这样可以看作二分图),这样的两个图乘起来对联通块的个数贡献是2.因为形如(u1,u2)->(v1,v2)和(u1,v2)->(v1,u2)的边是没有交集的,(这可以从这两个图没有奇环看出,因为v1,v2之间的距离的奇偶性是不会变的).

最后是至少一个图有奇环的情况,根据上面的情况可以得出v1,v2之间距离的奇偶因为存在奇环发生改变,所以对答案的贡献是1.

讨论完上面三种情况,这道题就可以做了.通过dfs统计出,单个点的数量cnt,有奇环的联通块数量p,没有奇环的联通块的数量q.答案 $a n s = c n t * c n t + 2 * c n t * (n - c n t) + p * p + 2 * p * q + 2 * q * q$

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

#define x first
#define y second
typedef pair<int,int> pii;
typedef long long ll;
const int MAXN=100005;

int n,m;
int co[MAXN];
bool vis[MAXN];
vector<int> E[MAXN];

bool dfs(int u){
    bool tag=1;
    vis[u]=1;
    for(int i=0;i<(int)E[u].size();i++){
        int v=E[u][i];
        if(vis[v]) tag&=(co[v]!=co[u]);
        else{
            co[v]=co[u]^1;
            tag&=dfs(v);
        }
    }
    return tag;
}

int main(){
    //freopen("squared.in","r",stdin);
    //freopen("squared.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    int cnt=0,p=0,q=0;
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        if(!E[i].size()) cnt++;
        else{
            if(dfs(i)) q++;
            else p++;
        }
    }
    printf("%lldn",(ll)cnt*cnt+2ll*cnt*(n-cnt)+p*p+2ll*p*q+2ll*q*q);

    fclose(stdin);
    fclose(stdout);
}