今年下半年,我将继续作为传送门 (雾)

很经典的环计数题目呢(可惜 qhy 现在才学到

首先我们记 $a[u][v]$表示 $u$到 $v$有多少条长度为 $1$的路径,$b[u][v]$表示 $u$到 $v$有多少条长度为 $2$的路径,记 $c[u][v]$表示 $u$到 $v$有多少条长度为 $3$的路径

这里的 $b$和 $c$可以 $n^3$用类似 $floyd$的搞法弄出来

然后我们枚举 $u$和 $v$,将 $b[u][v]\times c[u][v]$累加进答案里。

我们发现,因为这里你从 $5$个点里选了 $2$个出来,因此每个五元环多算了 $C_5^2=10$次,因此将现在的答案除以 $10$

注意到我们这样算会把某些退化的五元环也算进去,比如说

用手画几下就会发现,只有这一种情况 (即三元环并且直接外接一个点) 会产生退化的五元环,我们可以枚举三元环,再减去它们的度数和 $-3$即可

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define inf 1000000007
#define mod 1000003
#define N 705
#define ll long long
int a[N][N], b[N][N], c[N][N], u, v, n, m, d[N];
ll ans;
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, m)
    {
        scanf("%d %d", &u, &v);
        ++a[u][v]; ++a[v][u];
        ++d[u]; ++d[v];
    }
    fo (i, 1, n) fo (j, 1, n) fo (k, 1, n)
        b[i][j] += (a[i][k] * a[k][j]);
    fo (i, 1, n) fo (j, 1, n) fo (k, 1, n)
        c[i][j] += (a[i][k] * b[k][j]);
    fo (i, 1, n)
        fo (j, 1, n)
            ans += b[i][j] * c[i][j];
    ans /= 10;
    fo (i, 1, n)
        fo (j, 1, i)
            if (a[i][j])
                fo (k, 1, j)
                {
                    if (!(a[i][k] && a[j][k])) continue;
                    ans -= d[i] + d[j] + d[k] - 3;
                }
    printf("%lld\n", ans);        
    return 0;
}
分类: 文章

HomuraCat

明日は何になる? やがて君になる!

3 条评论

litble · 2019年1月4日 7:48 上午

灵魂画手……?

quhengyi11 · 2019年1月3日 6:45 下午

突然发现这一篇好像是第 666 篇(害怕.jpg,但愿 xzy 没有想过用这篇做纪念啥的 QAQ)

    Remmina · 2019年1月3日 7:21 下午

    Orz Dalao 好强啊
    赶紧向 Dalao 学习

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注