三元环小记(+四元环)

肯三竞赛·入门经典 - 多组赛配合理论 - 三元环

咳咳。

• P1989 无向图三元环计数

首先容易得到一个暴力 : 枚举3个点判断是否形成三元环,是O(n^3)的。

另一个暴力 : 枚举两条边判断两个外端点是否相连,复杂度O(m^2)

又一个暴力 : 枚举一个点及其对边,判断是否相连,复杂度O(nm)

容易发现我们只是在不断暴力就得到了更优的复杂度,我们考虑继续暴力。

考虑给每条边定向(任意),把度数小的点连向度数大的点,度数相同则比较编号。

容易得知原图变成了一个DAG,则形如(a\rightarrow b)(a\rightarrow c)(b\rightarrow c)的子图与三元环一一对应。

我们要枚举v,然后枚举v的出边判定,显然不划算。

对于判定,可以事先把u能够到达的所有点打上标记就可以O(1)了。

神奇的是,枚举次数变为了O(m\sqrt{m})

证明 :

枚举u点出边复杂度显然O(m)

• 对于度数为B的点

它的出边必然指向比它大的点,出度最多也就O(m/B)

做v点时,被点到B次(入度),每次贡献是O(m/B),单个点的贡献上界就是O(m)

• 对于对于度数大于\sqrt{m}的点(大度点)

最多O(\sqrt{m})个,这部分复杂度就是O(m\sqrt{m})

• 对于度数小于\sqrt{m}的点(小度点)

现在,做一次v的复杂度最多O(\sqrt{m}),入度总和也就O(m),复杂度也是O(m\sqrt{m})。

代码比较好写。

#include<algorithm>
#include<cstdio>
#include<vector>
#define sf scanf
#define MaxN 100500
using namespace std;
int n,m,du[MaxN],e[MaxN],ef,ans;
vector<int> g[MaxN];
struct Line{int f,t;}l[MaxN<<1];
void add(int x,int y)
{
  if (du[y]>du[x]||(du[x]==du[y]&&y<x))
    swap(x,y);
  g[x].push_back(y);
}
int main()
{
  sf("%d%d",&n,&m);
  for (int i=1,f,t;i<=m;i++){
    sf("%d%d",&l[i].f,&l[i].t);
    du[l[i].f]++;du[l[i].t]++;
  }for (int i=1;i<=m;i++)add(l[i].f,l[i].t);
  for (int u=1;u<=n;u++){
    ef=u;
    for (int i=0;i<g[u].size();i++)
      e[g[u][i]]=ef;
    for (int i=0;i<g[u].size();i++)
      for (int v=g[u][i],j=0;j<g[v].size();j++)
        if (e[g[v][j]]==ef)ans++;
  }printf("%d\n",ans);
  return 0;
}

• 四元环计数

类似地建立DAG

则(a\rightarrow b)(a\rightarrow c)(b\rightarrow d)(b\rightarrow d)的子图与四元环一一对应。

也就是说,统计d有多少种从a两步到达的方式,然后选取无序对即可。

至于怎么统计,一样考虑先枚举a,再枚举b,然后枚举b的所有出边。

最后把所有涉及到的点都拿出来统计即可。不难发现复杂度相同,为O(m\sqrt{m})。

• CF985G Team Players

题意 : 给出一张简单无向图,要求选出三个点互相之间没有边。

给定常数A,B,C,对于i<j<k,贡献为Ai+Bj+Ck,求贡献总和。

考虑容斥。

设F(k)=钦定k条边相连,其余随意的方案数。

不难得到$F(k)=\sum\limits_{i=k}^3\dbinom{k}{i}G(k)

二项式反演就得到G(k)=\sum\limits_{i=k}^3(-1)^{i-k}\dbinom{k}{i}F(k)

$F(2)$可以看作枚举同一个点的两条出边,按照出边编号排序,然后组合意义算一下。 $F(3)$就是三元环计数。