题解：CF51E Pentagon

ymt_QAQ · 2026-08-06 20:29:05 · 题解

题解：CF51E Pentagon

学校图论集训的一道题目，十分有意思。但我发现几乎所有的题解对删去不合法部分的叙述都略显简略，而正是这部分想了我一个多小时（或许是我太蒟蒻了？）。

切入点

定义：f_{l, i, j} 表示从 i 恰好走 l 步到达 j 的方案数。

这样定义有一个很自然的动机：一个五元环等价于从某点出发走 5 步再回到该点。不过目前这个说法还不够严谨，后面需要排除不合法的情况。

如果 u 与 v 相连，显然 f_{1, u, v} = 1；否则 f_{1, u, v} = 0。特别地，规定 f_{1, u, u} = 0。

接下来考虑如何扩展答案：

f_{l+1, u, v} = \sum_{k} f_{l, u, k} \times f_{1, k, v}

其中 k 是枚举的中转点。可以类比 Floyd 的思想来理解，这里实际上用的是刷表法：走 l+1 步可以由走 l 步和走 1 步拼接而成。

下面给出对应的代码片段：

for (int l = 1; l < 5; l++) {
    for (int k = 1; k <= n; k++)
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++) 
                dp[l + 1][u][v] += dp[l][u][k] * dp[1][k][v];
}

如果不加解释，很容易怀疑它的正确性：既没显式判相邻，也没限制顺序，更没有检查点是否重复——这样真的能行吗？

如果你已经想通了这些疑问，可以跳过下面的解释。否则，这里是我自己的思考过程，希望能帮你理解。

疑虑主要集中在两方面：

遍历的顺序（比如反向走一遍，为什么也要统计）；
点是否相同（起点、终点、中转点重合时是否合法）。

遍历的顺序

当中转点 k 变化时：只有当 k 与 v 相邻时，f_{1,k,v} 才可以，否则该项为 0 没有贡献。若 k 变了但仍然是 v 的邻居，由于到达 v 前的路径不同，整条路径必然不同；若 v 也改变，终点都不一样，自然更是新路径。因此 k 的变化总能产生全新路径，统计是必要的。
若 u, v 改变（非交换），起点和终点都变了，显然不是同一条路径。
若 u, v 交换：扩展式要求从 u 到 k 走 l-1 步、从 k 到 v 走 1 步。但反过来，从 v 到 k 走 1 步、k 到 u 走 l-1 步同样合法，且恰好对应 u,v 交换后的情况。因此交换 u,v 能自动覆盖反向路径，算法是完备的。

综上，该算法在遍历顺序上没有问题。

点是否相同

若 u = v = k：代入扩展式会出现 f_{1, u, u}，而我们初始化时已强制 f_{1, u, u}=0，相乘后贡献为 0，不会产生干扰。
若 u = v 且 k \neq u：这表示从 u 出发走了一圈回到自身，且经过了其他节点——正是我们要找的环，完全正确。
若 u = k 且不属于前两种情况：此时路径尚未明确，不应提前计入。代入式子恰好含有 f_{1, u, u}=0，贡献为 0，因此统计是安全的。

综上所述，该代码片段的正确性成立。

我们先钦定答案为 \dfrac{\sum_{i=1}^{n} f_{5, i, i}}{10}，后面再进行修正。

为什么要除以 10？因为一个五元环上有 5 个点，每个点都可以作为起点，并且可以按顺时针、逆时针两个方向走，因此同一个环会被重复计算 2 \times 5 = 10 次，除以 10 即可得到正确数量。

::::success[小提示（卡常）] 建议将步数 l 放在第一维，这样对缓存（也有可能是内存吧，记不清了）访问更友好，运行更快。 ::::

删去不合法

考虑下面这张图：

可以发现，有一些只涉及 4 个点的情况（例如 1,2,3,4）。如果沿着 1\to2\to3\to1\to4\to1 走，恰好是 5 条边，但它显然不是一个合法的五元环。必须将这类方案剔除。

令 \deg_i 表示点 i 的度数。先只看图中红色三角形衍生出的不合法方案：在三角形的基础上，额外走一条伸出去的边，就会形成不合法的“伪五元环”。
以点 1 为例，它可以向外走到 4,5,6，方案数即为 \deg_1 减去三角形内部的两个邻居（2,3）。对三角形的三个顶点都这样计算，合计有 (\deg_1-2)+(\deg_2-2)+(\deg_3-2) = \deg_1+\deg_2+\deg_3-6 种。

但这还没完：在三角形内部，也可能走出“点 1\to2\to1 再顺时针走一圈”这样的路径，同样正好 5 条边，而且只涉及 3 个点。这种情况下三条边都有可能被重复走一次，共有 3 种方案。因此需要从上面减去的方案中再加回 3，最终不合法的三角形贡献为 (\deg_1+\deg_2+\deg_3-6)+3 = \deg_1+\deg_2+\deg_3-3。

枚举三角形时务必保证三个顶点有序（例如 i<j<k），否则会重复减去而导致错误。

Code

/*
By ymt_QAQ
You must not copy this code.
You will become brown name and have a cute tag if you copy this code.
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 7e2 + 100;
long long dp[6][N][N];
int deg[N];
int e[N][N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++, deg[v]++;
        e[u][v] = e[v][u] = true;
        dp[1][u][v] = dp[1][v][u] = 1; // 别忘记初始化
    }
    for (int l = 1; l < 5; l++) {
        for (int k = 1; k <= n; k++)
            for (int u = 1; u <= n; u++)
                for (int v = 1; v <= n; v++) 
                    dp[l + 1][u][v] += dp[l][u][k] * dp[1][k][v];
    }
    long long ans = 0;
    for (int u = 1; u <= n; u++) {
        ans += dp[5][u][u];
    }
    ans /= 10;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (e[i][j] and e[j][k] and e[i][k]) // 判断是否为三角形
                    ans -= (deg[i] + deg[j] + deg[k] - 3);
            }
        }
    }
    cout << ans;
    return 0;
}

~~求一个小赞~~ 如果你 T 了，你可以把语言改为 c++20，亲测 c++17 不可过，但是 c++20 就行了 QAQ。

时间复杂度

大概是 O(n^3) 左右，但是还是会有 5 倍常数。

生成式 AI 使用说明

为了给管理员和读者提供良好的阅读体验，本题解使用 Gen AI 进行润色校准，下面是详细说明。

本篇题解中，DeepSeek 仅用于润色。详细对话历史见：这里，原文章见这里。