固定路径中间的有向边，左右两端独立从两侧端点的其余邻居中选择，边贡献就是两个度数减一的乘积。
OJ: luogu
题目 ID: P8605
难度:普及+/提高
标签:图论计数推导
日期: 2026-06-19 19:16
题意
给出一个无向图，要求统计长度恰好为 3 的有向转发路径数量：
a -> b -> c -> d
其中源点和终点可以相同，但两个中间点要和两端区分开。
思路
最直接的办法是暴力枚举四元组 (a, b, c, d)。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
static vector<vector<int>> g;
static int n;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin >> n >> m;
g.assign(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u][v] = g[v][u] = 1;
}
long long ans = 0;
for (int a = 1; a <= n; ++a) {
for (int b = 1; b <= n; ++b) {
if (!g[a][b]) {
continue;
}
for (int c = 1; c <= n; ++c) {
if (!g[b][c]) {
continue;
}
if (c == a || c == b) {
continue;
}
for (int d = 1; d <= n; ++d) {
if (!g[c][d]) {
continue;
}
if (d == b || d == c) {
continue;
}
// 源点和终点可以相同，但两个中间点必须和两端都区分开。
if (b == a || b == d || c == a || c == d) {
continue;
}
++ans;
}
}
}
}
cout << ans << '\n';
return 0;
}brute.cpp 会直接检查三条边是否存在，并判断中间点是否合法，适合小图对拍。
真正的关键是固定中间那条有向边。对于一条合法路径：
a -> b -> c -> d
中间边唯一就是 b -> c。一旦这条边方向固定：
- 左端
a只能从b的其他邻居里选 - 右端
d只能从c的其他邻居里选
这张图展示第二个样例里的小图结构：
graph G {
1 -- 2;
2 -- 3;
3 -- 1;
1 -- 4;
}
从这张图里可以看到，如果把 1 -> 2 当作中间边，那么左端只能从 1 的其余邻居 {3,4} 里选，右端只能从 2 的其余邻居 {3} 里选，所以这一条有向中间边贡献 2 * 1 = 2 条路径。其他边完全同理。
于是对每条无向边 (u, v)：
- 把它看成中间有向边
u -> v，贡献是(deg[u] - 1) * (deg[v] - 1) - 反过来
v -> u再算一次
把所有边贡献加起来就是答案。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u;
int v;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> deg(n + 1, 0);
vector<Edge> edges(m);
for (int i = 0; i < m; ++i) {
cin >> edges[i].u >> edges[i].v;
++deg[edges[i].u];
++deg[edges[i].v];
}
long long ans = 0;
for (const auto &e : edges) {
ans += 1LL * (deg[e.u] - 1) * (deg[e.v] - 1);
ans += 1LL * (deg[e.v] - 1) * (deg[e.u] - 1);
}
cout << ans << '\n';
return 0;
}复杂度
只需要统计度数并遍历一次边，所以时间复杂度是
总结
这题的关键不在于枚举整条路径，而在于抓住“中间边唯一决定左右独立选择”这个性质。固定中间边后，问题就变成了简单的度数乘法计数。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
