三元环小记(+四元环)

肯三竞赛·入门经典 - 多组赛配合理论 - 三元环 咳咳。 ------------ - [P1989 无向图三元环计数](https://www.luogu.com.cn/problem/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})$。 代码比较好写。 ```cpp #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](https://www.luogu.com.cn/problem/CF985G) **题意** : 给出一张简单无向图,要求选出三个点互相之间没有边。 给定常数$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)$就是三元环计数。