【题解】CF51E Pentagon 五元环计数 ——quhengyi11

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

很经典的环计数题目呢（可惜 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;
}