三元环小记(+四元环) 更新于 2026/7/5 11:03:51 作者

command_block

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

咳咳。

---

• 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$条边相连,其余随意的方案数。

$G(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(0)$即为任意三元组。$F(1)$枚举一条边计算即可。

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

$F(3)$就是三元环计数。