三元环计数学习笔记 || CF985G Team Players

· · 题解

本文着重讲解三元环计数问题。

三元环计数

题意

给你 n 个点 m 条边的无向图，求三元环的个数。m\le 2\times10^5。

题解

先考虑暴力。

枚举三元环中的其中一个点 u，再枚举 u 邻域中的一个点 v，再枚举 v 邻域中的一个点 w，判断 w 是否在 u 的邻域中。

枚举 u 和 v 实际上就是枚举了图中的边，所以暴力的时间复杂度是 O(m^2) 的。

我们考虑给无向边定向，把无向图变成 DAG。

我们按照度数把点排序，度数小的连向度数大的。为了使图为 DAG，当度数相同时，编号小的连向编号大的，不然可能连出环。

我们发现按度数连边，每个点的出度不会很大。

所以每个点的出度都 \le \sqrt m。

接下来我们只需要去统计形如 u\to v,v\to w,u\to w 的三元环，枚举 w 的这一步就优化成了 O(\sqrt m)。

总时间复杂度为 O(m\sqrt m)。

例题 CF985G Team Players

题意

给你 n 个点 m 条边的无向图。

如果一个点的三元组 (i,j,k)~(i<j<k) 两两无边，那么它的贡献为 A\times i+B\times j+C\times k。

求出所有三元组的贡献和。

题解

题解中点的编号从 1 开始。

直接做边太多了，考虑容斥。分四种情况考虑。

  1. 边数 \ge0。
    • 直接暴力数三元组即可。
    • 贡献为 \sum\limits_{i=1}^ni\times A\times \dbinom{n-i}{2}+\sum\limits_{i=1}^ni\times B\times (i-1)\times(n-i)+\sum\limits_{i=1}^ni\times C\times \dbinom{i-1}{2}
    • 时间复杂度 O(n)。
  2. 边数 \ge 1。
    • 枚举这条边 (u,v)，钦定 u<v，考虑第三个点 w 的位置。
    • w<u$ 时，贡献为 $\sum\limits_{w=1}^{u-1}w\times A+u\times B+v\times C=(u-1)\times (u\times B+v\times C)+\cfrac{u\times(u-1)}{2}\times A
    • u<w<v$ 时，贡献为 $\sum\limits_{w=u+1}^{v-1}u\times A+w\times B+v\times C=(u-v-1)\times (u\times A+v\times C)+\cfrac{(u+v)\times(u-v-1)}{2}\times B
    • v<w$ 时，贡献为 $\sum\limits_{w=v+1}^{n}u\times A+v\times B+w\times C=(n-v)\times (u\times A+v\times B)+\cfrac{(v+1+n)\times(n-v)}{2}\times C
    • 时间复杂度 O(m)。
  3. 边数 \ge 2。
    • 枚举两条边的交点 u，枚举 u 邻域中的点 v，考虑第三个点 w 的位置。钦定 w<v。
    • 设 rk 为邻域中编号小于 u 的点的数量，i 为 v 在邻域中的排名，cntr=\sum\limits_{i\in N(u),i\le rk}i，cntv=\sum\limits_{i\in N(u),i<v}i。
    • 当 w\le v\le u 时，贡献为 \sum\limits_{w\in N(u),w<v}w\times A+v\times B+u\times C=(i-1)\times(v\times B+u\times C)+cntv*A
    • 当 w\le u\le v 时，贡献为 \sum\limits_{w\in N(u),w<u}w\times A+u\times B+v\times C=rk\times(u\times B+v\times C)+cntr*A
    • 当 u\le w\le v 时，贡献为 \sum\limits_{w\in N(u),u<w<v}u\times A+w\times B+v\times C=(v-rk-1)\times(u\times A+v\times C)+(cntv-cntr)*B
    • 时间复杂度 O(m)。
  4. 边数 \ge 3。
    • 其实就是三元环计数。时间复杂度 O(m\sqrt m)。

简单容斥可得 ANS=Cnt_0-Cnt_1+Cnt_2-Cnt_3。

代码

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=2e5+10;
int n,m,d[N],vis[N];
ll C0,C1,C2,C3,A,B,C;
int fst[N<<1],to[N<<1],nxt[N<<1],ecnt;
void adde(int u,int v){
    ecnt++;
    to[ecnt]=v;
    nxt[ecnt]=fst[u];
    fst[u]=ecnt;
}
struct edge{int u,v;}E[N];
vector<int>e[N];
int main(){
    cin>>n>>m>>A>>B>>C;
    for(int i=1;i<=n;i++){//0
        C0+=(ll)(n-i)*(n-i-1)/2*A*(i-1);
        C0+=(ll)(i-1)*(n-i)*B*(i-1);
        C0+=(ll)(i-1)*(i-2)/2*C*(i-1);
    }
    for(int i=1;i<=n;i++)e[i].push_back(0);
    for(int i=1,u,v;i<=m;i++){//1
        cin>>u>>v;u++,v++;
        d[u]++,d[v]++;
        E[i]=(edge){u,v};
        e[u].push_back(v);
        e[v].push_back(u);
        if(u>v)swap(u,v);
        C1+=(u-1)*((u-1)*B+(v-1)*C)+(ll)(u-2)*(u-1)/2*A;
        C1+=(v-u-1)*((u-1)*A+(v-1)*C)+(ll)(v+u-2)*(v-u-1)/2*B;
        C1+=(n-v)*((u-1)*A+(v-1)*B)+(ll)(v+n-1)*(n-v)/2*C;
    }
    for(int i=1;i<=n;i++)sort(e[i].begin(),e[i].end());
    for(int u=1;u<=n;u++){//2
        ll rk=0,cntr=0,cnt=0;
        for(int i=1;i<=d[u];i++){
            if(e[u][i]<u)rk=i,cntr+=e[u][i]-1;
            else break;
        }
        for(int i=1;i<=d[u];i++){
            int v=e[u][i];
            if(v<u)C2+=(i-1)*((u-1)*C+(v-1)*B)+cnt*A;
            else{
                C2+=(i-rk-1)*((u-1)*A+(v-1)*C)+(cnt-cntr)*B;
                C2+=rk*((u-1)*B+(v-1)*C)+cntr*A;
            }
            cnt+=v-1;
        }
    }
    for(int i=1;i<=m;i++){
        if(d[E[i].u]<d[E[i].v]||(d[E[i].u]==d[E[i].v]&&E[i].u<E[i].v))adde(E[i].u,E[i].v);//注意这一行 
        else adde(E[i].v,E[i].u);
    }
    for(int u=1;u<=n;u++){//3
        for(int i=fst[u];i;i=nxt[i])vis[to[i]]=1;
        for(int i=fst[u];i;i=nxt[i]){
            int v=to[i];
            for(int j=fst[v];j;j=nxt[j]){
                int w=to[j];
                if(vis[w])C3+=(min({u,v,w})-1)*A+(u+v+w-min({u,v,w})-max({u,v,w})-1)*B+(max({u,v,w})-1)*C;
            }
        }
        for(int i=fst[u];i;i=nxt[i])vis[to[i]]=0;
    }
    cout<<C0-C1+C2-C3;
}