科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文基于 codeforces-go 仓库中 LeetCode 第 119 场双周赛 D 题LeetCode 2959Number of Possible Sets of Closing Branches的题解文档系统讲解两类解法二进制枚举 Floyd与状压 DP Floyd。你将掌握枚举保留节点集合 任意两点最短路校验的标准套路并深入理解如何把经典三维 Floyd DP 改造成以中间节点集合为状态的子集转移形式从而把每次子集的最短路计算从 O(n³) 降到 O(n²)。文中所有代码与复杂度结论均有仓库源码与测试用例可查证。题目背景关闭分支的可行方案数本题来自 LeetCode 双周赛第 119 场 D 题题目编号为LeetCode 2959题解文档位于 leetcode/biweekly/119/d/README.md仓库中对应的 Go 实现见 d.go测试用例文件为 d.txt。问题定义给定节点编号 $0,1,\cdots,n-1$共 $n$ 个节点参数 $\textit{maxDistance}$阈值距离$\textit{roads}$无向带权边列表每条边为 $[x,y,wt]$。允许关闭删除任意数量的节点。问有多少种方案使得保留下来的节点中任意两点之间的最短路长度都不超过 $\textit{maxDistance}$关闭节点的方案可以不同只要保留的节点集合满足上述约束就算一种方案。需要注意的是本题统计的是满足条件的保留节点集合数量空集、单点集也符合条件例如 $S\varnothing$ 与 $S{0}$ 都必然满足返回值为方案数。核心难点直接枚举保留集合 $S \subseteq {0,1,\cdots,n-1}$ 共有 $2^n$ 种对每个 $S$ 又要计算保留节点间的全源最短路。如何让枚举 求最短路的总代价可承受是本题的两条主线方法一朴素枚举每个子集用完整 Floyd 计算复杂度 $\mathcal{O}(m n^3 \cdot 2^n)$方法二状压转移利用子集间的递推关系每个子集只用 $\mathcal{O}(n^2)$ 增量计算复杂度 $\mathcal{O}(m n^2 \cdot 2^n)$。当 $n$ 较大本题 $n$ 不超过 10 左右时$2^n$ 枚举可行而 $n^3 \cdot 2^n$ 与 $n^2 \cdot 2^n$ 的差距在 $n$ 接近上限时尤为关键。方法一二进制枚举 Floyd思路枚举 ${0,1,2,\cdots,n-1}$ 的所有子集 $S$作为保留的节点集合关闭删除不在 $S$ 中的节点。随后用 Floyd 求出保留节点之间的最短路若这些最短路均不超过 $\textit{maxDistance}$则答案加一。枚举子集的技巧源自从集合论到位运算中「枚举集合」的经典做法用整数 $s$ 的二进制位表示集合从 $0$ 遍历到 $2^n-1$第 $i$ 位为 1 表示节点 $i$ 在集合中判断用s i 1。关键优化预预处理邻接矩阵代码实现时可以先预处理原图的邻接矩阵 $g$这样无需每次枚举子集都重新遍历一次 $\textit{roads}$。对每个子集 $s$只需拷贝 $g$ 中保留的节点对应行即可。伪码流程构建邻接矩阵 $g$无向边双向写入取重边最小值$g[i][i]0$不存在的边初始化为一个大数如INT_MAX / 2防止加法溢出遍历 $s \in [0, 2^n)$拷贝保留节点的行到矩阵 $f$在 $f$ 上运行 Floyd只以 $S$ 中的节点为中转点也只考虑 $S$ 中的 $i,j$校验所有 $i,j \in S$ 的 $f[i][j] \le \textit{maxDistance}$通过则答案加一。参考实现Python3class Solution: def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) - int: g [[inf] * n for _ in range(n)] for x, y, wt in roads: g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) f [None] * n def check(s: int) - int: for i, row in enumerate(g): if s i 1: # i 在集合 s 中 f[i] row.copy() # Floyd 算法只考虑在 s 中的节点 for k in range(n): if (s k 1) 0: # k 不在集合 s 中 continue for i in range(n): if (s i 1) 0 or f[i][k] inf: continue for j in range(n): f[i][j] min(f[i][j], f[i][k] f[k][j]) # 判断保留的节点之间的最短路是否均不超过 maxDistance for i, di in enumerate(f): if (s i 1) 0: # i 不在集合 s 中 continue for j, dij in enumerate(di[:i]): if s j 1 and dij maxDistance: return 0 return 1 # 枚举子集 s作为保留的节点判断这些节点否满足要求 return sum(check(s) for s in range(1 n))Javaclass Solution { public int numberOfSets(int n, int maxDistance, int[][] roads) { int[][] g new int[n][n]; for (int[] row : g) { Arrays.fill(row, Integer.MAX_VALUE / 2); // 防止加法溢出 } for (int[] e : roads) { int x e[0]; int y e[1]; int wt e[2]; g[x][y] Math.min(g[x][y], wt); g[y][x] Math.min(g[y][x], wt); } int ans 0; int[][] f new int[n][n]; next: for (int s 0; s (1 n); s) { for (int i 0; i n; i) { if ((s i 1) 1) { System.arraycopy(g[i], 0, f[i], 0, n); } } // Floyd 算法只考虑在 s 中的节点 for (int k 0; k n; k) { if ((s k 1) 0) continue; for (int i 0; i n; i) { if ((s i 1) 0) continue; for (int j 0; j n; j) { f[i][j] Math.min(f[i][j], f[i][k] f[k][j]); } } } // 判断保留的节点之间的最短路是否均不超过 maxDistance for (int i 0; i n; i) { if ((s i 1) 0) continue; for (int j 0; j i; j) { if ((s j 1) 1 f[i][j] maxDistance) { continue next; } } } ans; } return ans; } }Cclass Solution { public: int numberOfSets(int n, int maxDistance, vectorvectorint roads) { vectorvectorint g(n, vectorint(n, INT_MAX / 2)); // 防止加法溢出 for (auto e: roads) { int x e[0], y e[1], wt e[2]; g[x][y] min(g[x][y], wt); g[y][x] min(g[y][x], wt); } vectorvectorint f(n); auto check - bool { for (int i 0; i n; i) { if ((s i) 1) { f[i] g[i]; } } // Floyd 算法只考虑在 s 中的节点 for (int k 0; k n; k) { if (((s k) 1) 0) continue; for (int i 0; i n; i) { if (((s i) 1) 0) continue; for (int j 0; j n; j) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } // 判断保留的节点之间的最短路是否均不超过 maxDistance for (int i 0; i n; i) { if (((s i) 1) 0) continue; for (int j 0; j i; j) { if ((s j) 1 f[i][j] maxDistance) { return false; } } } return true; }; int ans 0; for (int s 0; s (1 n); s) { // 枚举子集 ans check(s); } return ans; } };Gofunc numberOfSets(n, maxDistance int, roads [][]int) (ans int) { g : make([][]int, n) for i : range g { g[i] make([]int, n) for j : range g[i] { g[i][j] math.MaxInt / 2 // 防止加法溢出 } } for _, e : range roads { x, y, wt : e[0], e[1], e[2] g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) } f : make([][]int, n) for i : range f { f[i] make([]int, n) } next: for s : 0; s 1n; s { // 枚举子集 for i, row : range g { if si1 0 { continue } copy(f[i], row) } // Floyd 算法只考虑在 s 中的节点 for k : range f { if sk1 0 { continue } for i : range f { if si1 0 { continue } for j : range f { f[i][j] min(f[i][j], f[i][k]f[k][j]) } } } // 判断保留的节点之间的最短路是否均不超过 maxDistance for i, di : range f { if si1 0 { continue } for j, dij : range di[:i] { if sj1 0 dij maxDistance { continue next } } } ans } return }复杂度分析时间复杂度$\mathcal{O}(m n^3\cdot 2^n)$其中 $m$ 为 $\textit{roads}$ 的长度建图 $O(m)$每个子集跑一次 $O(n^3)$ 的 Floyd共 $2^n$ 个子集。空间复杂度$\mathcal{O}(n^2)$邻接矩阵 $g$ 与工作矩阵 $f$。仓库实现佐证方法一在仓库中的实现是 d.go 中的numberOfSets2第 56 行起。它与文档版有一处细节差异初始化时显式置g[i][i] 0对应注释g[i][i] 0也可以不加这个 if下面判断 maxDistance 时要保证 j ! i因此校验阶段可以遍历完整的行而不必用di[:i]——因为 $f[i][i]0$ 恒不大于非负的maxDistance对角线不会触发非法判断。两种写法等价文档版通过j i利用无向图对称性只检查一半点对仓库版则依赖对角线为 0 的设定殊途同归。仓库模板库 copypasta/graph.go 中的floydShortestPath约第 1965 行起给出了标准 Floyd-Warshall 的完整实现与注释其中也包含了与本题直接相关的两个优化点中转循环里if f[i][mid] inf { continue }针对稀疏图跳过无用迭代注释中特别指出计算完 $f[i][j]$ 后要判断所有 $f[i][j]$可利用 $f[i][j]f[j][i]$ 的性质只判断j i的情况减少一半计算量——这正是上述di[:i]/j i写法的由来。方法二状压 DP Floyd从三维 Floyd 出发改造状态定义回顾三维 Floyd DP 的定义$f[k][i][j]$从 $i$ 到 $j$ 的最短路长度并且这条最短路的中间节点编号都 $\le k$。方法二把中间节点编号不超过 $k$推广为中间节点编号属于集合 $S$以便在子集之间做增量转移$f[S][i][j]$从 $i$ 到 $j$ 的最短路长度并且这条最短路的中间节点编号在集合 $S$ 中。状态转移方程假设已经算出了 $T$ 的 $f[T]$现在要计算 $S T \cup {k}$ 的 $f[S]$。节点 $k$ 带来的影响只有两种可能不影响 $i$ 到 $j$ 的最短路$f[S][i][j] f[T][i][j]$影响 $i$ 到 $j$ 的最短路即经过 $k$ 更短$f[S][i][j] f[T][i][k] f[T][k][j]$。二者取最小值得核心递推式$$ f[S][i][j] \min(f[T][i][j], f[T][i][k] f[T][k][j]) $$初始值与经典 Floyd 一致$$ f[\varnothing][i][j] g[i][j] $$即 $\textit{roads}$ 中 $i$ 到 $j$ 这条边的长度无边则为 $\infty$$g[i][i]0$。增量收益上述递推意味着每多算一个子集 $S$只需要 $\mathcal{O}(n^2)$ 的时间就可以得到该集合下任意点对的最短路——而方法一每个子集都要跑完整的 $\mathcal{O}(n^3)$ Floyd。这是两个方法时间复杂度的本质差距来源$n^3\cdot2^n$ vs $n^2\cdot2^n$。关键理解$S$ 是中间节点集合不是保留节点集合⚠️ 需要注意该计算过程不需要保证 $i$ 和 $j$ 都是 $S$ 中的元素$S$ 只是中间节点的编号集合不是保留的编号集合。但是如果设 $i$ 和 $j$ 都是 $S$ 中的元素那么从点 $i$ 到点 $j$、只经过 $S$ 中节点的情况下最短路长度恰好就是 $f[S][i][j]$。因此在「$i$ 和 $j$ 都是 $S$ 中的元素」的前提下$S$ 也可以直接当作当前保留的节点集合来用$f[S][i][j]$ 可以用来与 $\textit{maxDistance}$ 比较大小——这正是本题将子集最短路的增量计算与保留集合校验合二为一的关键。实现要点枚举 $S$ 时节点 $k$ 可以是 $S$ 中的任一元素比如最小元素或最大元素。各语言惯用取法Pythons.bit_length() - 1最高位、JavaInteger.numberOfTrailingZeros(s)与 C__builtin_ctz(s)与 Gobits.TrailingZeros(s)最低位。随后t s ^ (1 k)去掉 $k$ 得到 $T$即可从 $f[T]$ 递推 $f[S]$在计算 $f[S][i][j]$ 的同时可以同步检查「$i,j \in S$ 且 $f[S][i][j] \textit{maxDistance}$」一旦违反立刻把当前 $S$ 标记为不合法避免二次遍历由于 $f[S][i][j] f[S][j][i]$只需检查j i的一半点对$S\varnothing$即 $s0$必然满足条件没有保留任何节点或等价地保留节点间无需校验答案初始化为 1。参考实现Python3class Solution: def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) - int: g [[inf] * n for _ in range(n)] for x, y, wt in roads: g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) ans 1 # s0 一定满足要求 f [[[inf] * n for _ in range(n)] for _ in range(1 n)] f[0] g for s in range(1, 1 n): k s.bit_length() - 1 t s ^ (1 k) ok 1 for i in range(n): for j in range(n): f[s][i][j] min(f[t][i][j], f[t][i][k] f[t][k][j]) # 手动求 min 可以更快 if ok and j i and s i 1 and s j 1 and f[s][i][j] maxDistance: ok 0 ans ok return ansJavaclass Solution { public int numberOfSets(int n, int maxDistance, int[][] roads) { int[][] g new int[n][n]; for (int[] row : g) { Arrays.fill(row, Integer.MAX_VALUE / 2); } for (int[] e : roads) { int x e[0]; int y e[1]; int wt e[2]; g[x][y] Math.min(g[x][y], wt); g[y][x] Math.min(g[y][x], wt); } int ans 1; // s0 一定满足要求 int[][][] f new int[1 n][n][n]; for (int[][] matrix : f) { for (int[] row : matrix) { Arrays.fill(row, Integer.MAX_VALUE / 2); } } f[0] g; for (int s 1; s (1 n); s) { int k Integer.numberOfTrailingZeros(s); int t s ^ (1 k); boolean ok true; for (int i 0; i n; i) { for (int j 0; j n; j) { f[s][i][j] Math.min(f[t][i][j], f[t][i][k] f[t][k][j]); if (ok j i (s i 1) ! 0 (s j 1) ! 0 f[s][i][j] maxDistance) { ok false; } } } ans ok ? 1 : 0; } return ans; } }Cclass Solution { public: int numberOfSets(int n, int maxDistance, vectorvectorint roads) { vectorvectorint g(n, vectorint(n, INT_MAX / 2)); for (auto e: roads) { int x e[0], y e[1], wt e[2]; g[x][y] min(g[x][y], wt); g[y][x] min(g[y][x], wt); } int ans 1; // s0 一定满足要求 vectorvectorvectorint f(1 n, vectorvectorint(n, vectorint(n, INT_MAX / 2))); f[0] g; for (int s 1; s (1 n); s) { int k __builtin_ctz(s); int t s ^ (1 k); bool ok true; for (int i 0; i n; i) { for (int j 0; j n; j) { f[s][i][j] min(f[t][i][j], f[t][i][k] f[t][k][j]); if (ok j i (s i 1) (s j 1) f[s][i][j] maxDistance) { ok false; } } } ans ok; } return ans; } };Gofunc numberOfSets(n, maxDistance int, roads [][]int) int { g : make([][]int, n) for i : range g { g[i] make([]int, n) for j : range g[i] { g[i][j] math.MaxInt / 2 // 防止加法溢出 } } for _, e : range roads { x, y, wt : e[0], e[1], e[2] g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) } ans : 1 // s0 一定满足要求 f : make([][][]int, 1n) for i : range f { f[i] make([][]int, n) for j : range f[i] { f[i][j] make([]int, n) for k : range f[i][j] { f[i][j][k] math.MaxInt / 2 } } } f[0] g for s : uint(1); s 1n; s { k : bits.TrailingZeros(s) t : s ^ (1 k) ok : true for i : 0; i n; i { for j : 0; j n; j { f[s][i][j] min(f[t][i][j], f[t][i][k]f[t][k][j]) if ok j i si1 ! 0 sj1 ! 0 f[s][i][j] maxDistance { ok false } } } if ok { ans } } return ans }复杂度分析时间复杂度$\mathcal{O}(m n^2\cdot 2^n)$其中 $m$ 为 $\textit{roads}$ 的长度。建图 $O(m)$每个子集仅用 $O(n^2)$ 从上一子集增量转移并同步校验共 $2^n$ 个子集。空间复杂度$\mathcal{O}(n^2\cdot 2^n)$需要为每个子集保存一张 $n\times n$ 的矩阵 $f[S]$。仓库实现佐证方法二正是仓库 d.go 中最终采用的numberOfSets实现第 9 行起。对比可发现初始化阶段显式保证g[i][i] 0注释g[i][i] 0也可以不加这个 if下面判断 maxDistance 时要保证 j ! i避免自环最短路干扰校验状态转移使用k : bits.TrailingZeros(s)选取 $S$ 的最小元素作为新增中转节点t : s ^ (1 k)得到去掉 $k$ 的 $T$递推式与文档完全一致校验与转移合并进同一双层循环ok一旦置 false 就不再比较短路同时利用j i只检查一半点对。此外模板库 copypasta/graph.go 的floydSubset约第 2060 行起把这一套路抽象成了可复用的模板函数注释明确标注了题目来源LC2959状态定义、bits.TrailingZeros(s)选 $k$、j i半矩阵校验等关键步骤与题解一一对应可以作为这类子集最短路题目的通用框架。测试验证仓库的自动化用例仓库为本题配置了完整的本地测试链测试入口 d_test.go通过testutil.RunLeetCodeFuncWithFile(t, numberOfSets, d.txt, targetCaseNum)读取 d.txt 中的用例并逐组断言targetCaseNum为 0 表示运行全部用例用例解析由 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile第 340 行起完成按每 $fNumIn fNumOut$ 行一组数据切分本题为 3 行输入 1 行输出再交给RunLeetCodeFuncWithExamples做反射调用、超时检测与输出比对。d.txt 中包含 3 组用例nmaxDistanceroads期望输出35[[0,1,2],[1,2,10],[0,2,10]]535[[0,1,20],[0,1,10],[1,2,2],[0,2,2]]7110[]2可以手动核对第一组3 个节点、阈值 5任意两节点之间要么直接相邻$0$-$1$ 长 2要么经 1 中转$0$-$2$ 长 12、$1$-$2$ 长 10 均超阈值因此只有 $\varnothing$、三个单点集以及 ${0,1}$ 共 5 种方案。最后一组 $n1$、无边空集与单点集各算一种答案恰为 2验证了$s0$ 一定满足要求、答案从 1 起算的初始化逻辑。若想本地复现在该仓库目录下运行go test ./leetcode/biweekly/119/d -run Test_d -v测试所需依赖见仓库根目录的 go.mod。同类题目与延伸练习本题融合了全源最短路Floyd与二进制枚举/状压两条知识线文档末尾给出了对应的练习清单可依难度循序渐进Floyd 相关题号后的数字为难度分设计可以求最短路径的图类1811动态加边的 Floyd与模板库floydShortestPath中addEdge注释见 copypasta/graph.go 第 2003 行附近对应阈值距离内邻居最少的城市1855Floyd 后统计阈值内邻居数是理解本题校验环节的入门题转换字符串的最小成本 I1882与 2977. 转换字符串的最小成本 II2696Floyd 与 DP 的进一步组合。二进制枚举相关子集、77. 组合枚举集合的基础功字母组合迭代器1591、2397. 被列覆盖的最多行数1719、2212. 射箭比赛中的最大得分1869基于陈述统计最多好人数1980、1601. 最多可达成的换楼请求数目2119、1617. 统计子树中城市之间最大距离2309——后几题已接近本题的枚举 图结构校验组合难度。模板库 copypasta/graph.go 中与该题直接相关的还有位压缩版 FloydfloydBitset第 2032 行起把布尔可达性压缩进Bitset单次或运算合并整行可达点复杂度 $\mathcal{O}(n^3/w)$$w$ 为机器字长适用于传递闭包类问题标准 FloydfloydShortestPath第 1965 行起含动态加边、负环检测、稀疏图剪枝等通用扩展。小结本题的两种解法恰好展示了枚举所有子集这一类问题的两条优化路径方法一二进制枚举 Floyd思路直接、实现简单每个子集独立跑最短路代价是 $\mathcal{O}(n^3\cdot2^n)$ 的总复杂度适合 $n$ 较小的场景方法二状压 DP Floyd把 Floyd 的三维状态从编号前缀推广为节点集合利用子集间的增量递推把每个子集的最短路计算降为 $\mathcal{O}(n^2)$总复杂度 $\mathcal{O}(n^2\cdot2^n)$以 $\mathcal{O}(n^2\cdot2^n)$ 空间换取时间。关键要点可总结为三条预处理邻接矩阵避免重复建图牢记$S$ 是中间节点集合、仅在 $i,j\in S$ 时作为保留集合校验这一状态语义利用 $f[S][i][j]f[S][j][i]$ 的对称性只校验j i的一半点对。仓库中 d.go 的两种实现、copypasta/graph.go 的floydSubset模板以及 d.txt 的测试用例可以作为你复现与扩展这套思路的可靠参照。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐3步掌握模块化游戏模组管理开源Mod Loader完全指南3步掌握模块化游戏模组管理开源Mod Loader完全指南 Mod Loader是一款专为《侠盗猎车手》III、罪恶都市和圣安地列斯设计的革命性模组管理工具游戏开发单调队列优化 DP 实战LeetCode 2945「找到最大非递减数组的长度」——codeforces-go 题解深度解析单调队列优化 DP 实战LeetCode 2945「找到最大非递减数组的长度」——codeforces go 题解深度解析 本篇技术指南以 LeetCode科学计算解锁codeforces-go从入门到精通的区间DP与环形DP实战指南解锁codeforces go从入门到精通的区间DP与环形DP实战指南 在算法竞赛的世界里动态规划DP是解决复杂问题的核心武器之一。而codeforce科学计算上一篇5 步生成可用的 OpenCore EFI黑苹果工具 OpCore-Simplify 完整实操指南下一篇终极Windows窗口调整神器3分钟学会强制修改任意窗口大小创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文基于 codeforces-go 仓库中 LeetCode 第 119 场双周赛 D 题LeetCode 2959Number of Possible Sets of Closing Branches的题解文档系统讲解两类解法二进制枚举 Floyd与状压 DP Floyd。你将掌握枚举保留节点集合 任意两点最短路校验的标准套路并深入理解如何把经典三维 Floyd DP 改造成以中间节点集合为状态的子集转移形式从而把每次子集的最短路计算从 O(n³) 降到 O(n²)。文中所有代码与复杂度结论均有仓库源码与测试用例可查证。题目背景关闭分支的可行方案数本题来自 LeetCode 双周赛第 119 场 D 题题目编号为LeetCode 2959题解文档位于 leetcode/biweekly/119/d/README.md仓库中对应的 Go 实现见 d.go测试用例文件为 d.txt。问题定义给定节点编号 $0,1,\cdots,n-1$共 $n$ 个节点参数 $\textit{maxDistance}$阈值距离$\textit{roads}$无向带权边列表每条边为 $[x,y,wt]$。允许关闭删除任意数量的节点。问有多少种方案使得保留下来的节点中任意两点之间的最短路长度都不超过 $\textit{maxDistance}$关闭节点的方案可以不同只要保留的节点集合满足上述约束就算一种方案。需要注意的是本题统计的是满足条件的保留节点集合数量空集、单点集也符合条件例如 $S\varnothing$ 与 $S{0}$ 都必然满足返回值为方案数。核心难点直接枚举保留集合 $S \subseteq {0,1,\cdots,n-1}$ 共有 $2^n$ 种对每个 $S$ 又要计算保留节点间的全源最短路。如何让枚举 求最短路的总代价可承受是本题的两条主线方法一朴素枚举每个子集用完整 Floyd 计算复杂度 $\mathcal{O}(m n^3 \cdot 2^n)$方法二状压转移利用子集间的递推关系每个子集只用 $\mathcal{O}(n^2)$ 增量计算复杂度 $\mathcal{O}(m n^2 \cdot 2^n)$。当 $n$ 较大本题 $n$ 不超过 10 左右时$2^n$ 枚举可行而 $n^3 \cdot 2^n$ 与 $n^2 \cdot 2^n$ 的差距在 $n$ 接近上限时尤为关键。方法一二进制枚举 Floyd思路枚举 ${0,1,2,\cdots,n-1}$ 的所有子集 $S$作为保留的节点集合关闭删除不在 $S$ 中的节点。随后用 Floyd 求出保留节点之间的最短路若这些最短路均不超过 $\textit{maxDistance}$则答案加一。枚举子集的技巧源自从集合论到位运算中「枚举集合」的经典做法用整数 $s$ 的二进制位表示集合从 $0$ 遍历到 $2^n-1$第 $i$ 位为 1 表示节点 $i$ 在集合中判断用s i 1。关键优化预预处理邻接矩阵代码实现时可以先预处理原图的邻接矩阵 $g$这样无需每次枚举子集都重新遍历一次 $\textit{roads}$。对每个子集 $s$只需拷贝 $g$ 中保留的节点对应行即可。伪码流程构建邻接矩阵 $g$无向边双向写入取重边最小值$g[i][i]0$不存在的边初始化为一个大数如INT_MAX / 2防止加法溢出遍历 $s \in [0, 2^n)$拷贝保留节点的行到矩阵 $f$在 $f$ 上运行 Floyd只以 $S$ 中的节点为中转点也只考虑 $S$ 中的 $i,j$校验所有 $i,j \in S$ 的 $f[i][j] \le \textit{maxDistance}$通过则答案加一。参考实现Python3class Solution: def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) - int: g [[inf] * n for _ in range(n)] for x, y, wt in roads: g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) f [None] * n def check(s: int) - int: for i, row in enumerate(g): if s i 1: # i 在集合 s 中 f[i] row.copy() # Floyd 算法只考虑在 s 中的节点 for k in range(n): if (s k 1) 0: # k 不在集合 s 中 continue for i in range(n): if (s i 1) 0 or f[i][k] inf: continue for j in range(n): f[i][j] min(f[i][j], f[i][k] f[k][j]) # 判断保留的节点之间的最短路是否均不超过 maxDistance for i, di in enumerate(f): if (s i 1) 0: # i 不在集合 s 中 continue for j, dij in enumerate(di[:i]): if s j 1 and dij maxDistance: return 0 return 1 # 枚举子集 s作为保留的节点判断这些节点否满足要求 return sum(check(s) for s in range(1 n))Javaclass Solution { public int numberOfSets(int n, int maxDistance, int[][] roads) { int[][] g new int[n][n]; for (int[] row : g) { Arrays.fill(row, Integer.MAX_VALUE / 2); // 防止加法溢出 } for (int[] e : roads) { int x e[0]; int y e[1]; int wt e[2]; g[x][y] Math.min(g[x][y], wt); g[y][x] Math.min(g[y][x], wt); } int ans 0; int[][] f new int[n][n]; next: for (int s 0; s (1 n); s) { for (int i 0; i n; i) { if ((s i 1) 1) { System.arraycopy(g[i], 0, f[i], 0, n); } } // Floyd 算法只考虑在 s 中的节点 for (int k 0; k n; k) { if ((s k 1) 0) continue; for (int i 0; i n; i) { if ((s i 1) 0) continue; for (int j 0; j n; j) { f[i][j] Math.min(f[i][j], f[i][k] f[k][j]); } } } // 判断保留的节点之间的最短路是否均不超过 maxDistance for (int i 0; i n; i) { if ((s i 1) 0) continue; for (int j 0; j i; j) { if ((s j 1) 1 f[i][j] maxDistance) { continue next; } } } ans; } return ans; } }Cclass Solution { public: int numberOfSets(int n, int maxDistance, vectorvectorint roads) { vectorvectorint g(n, vectorint(n, INT_MAX / 2)); // 防止加法溢出 for (auto e: roads) { int x e[0], y e[1], wt e[2]; g[x][y] min(g[x][y], wt); g[y][x] min(g[y][x], wt); } vectorvectorint f(n); auto check - bool { for (int i 0; i n; i) { if ((s i) 1) { f[i] g[i]; } } // Floyd 算法只考虑在 s 中的节点 for (int k 0; k n; k) { if (((s k) 1) 0) continue; for (int i 0; i n; i) { if (((s i) 1) 0) continue; for (int j 0; j n; j) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } // 判断保留的节点之间的最短路是否均不超过 maxDistance for (int i 0; i n; i) { if (((s i) 1) 0) continue; for (int j 0; j i; j) { if ((s j) 1 f[i][j] maxDistance) { return false; } } } return true; }; int ans 0; for (int s 0; s (1 n); s) { // 枚举子集 ans check(s); } return ans; } };Gofunc numberOfSets(n, maxDistance int, roads [][]int) (ans int) { g : make([][]int, n) for i : range g { g[i] make([]int, n) for j : range g[i] { g[i][j] math.MaxInt / 2 // 防止加法溢出 } } for _, e : range roads { x, y, wt : e[0], e[1], e[2] g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) } f : make([][]int, n) for i : range f { f[i] make([]int, n) } next: for s : 0; s 1n; s { // 枚举子集 for i, row : range g { if si1 0 { continue } copy(f[i], row) } // Floyd 算法只考虑在 s 中的节点 for k : range f { if sk1 0 { continue } for i : range f { if si1 0 { continue } for j : range f { f[i][j] min(f[i][j], f[i][k]f[k][j]) } } } // 判断保留的节点之间的最短路是否均不超过 maxDistance for i, di : range f { if si1 0 { continue } for j, dij : range di[:i] { if sj1 0 dij maxDistance { continue next } } } ans } return }复杂度分析时间复杂度$\mathcal{O}(m n^3\cdot 2^n)$其中 $m$ 为 $\textit{roads}$ 的长度建图 $O(m)$每个子集跑一次 $O(n^3)$ 的 Floyd共 $2^n$ 个子集。空间复杂度$\mathcal{O}(n^2)$邻接矩阵 $g$ 与工作矩阵 $f$。仓库实现佐证方法一在仓库中的实现是 d.go 中的numberOfSets2第 56 行起。它与文档版有一处细节差异初始化时显式置g[i][i] 0对应注释g[i][i] 0也可以不加这个 if下面判断 maxDistance 时要保证 j ! i因此校验阶段可以遍历完整的行而不必用di[:i]——因为 $f[i][i]0$ 恒不大于非负的maxDistance对角线不会触发非法判断。两种写法等价文档版通过j i利用无向图对称性只检查一半点对仓库版则依赖对角线为 0 的设定殊途同归。仓库模板库 copypasta/graph.go 中的floydShortestPath约第 1965 行起给出了标准 Floyd-Warshall 的完整实现与注释其中也包含了与本题直接相关的两个优化点中转循环里if f[i][mid] inf { continue }针对稀疏图跳过无用迭代注释中特别指出计算完 $f[i][j]$ 后要判断所有 $f[i][j]$可利用 $f[i][j]f[j][i]$ 的性质只判断j i的情况减少一半计算量——这正是上述di[:i]/j i写法的由来。方法二状压 DP Floyd从三维 Floyd 出发改造状态定义回顾三维 Floyd DP 的定义$f[k][i][j]$从 $i$ 到 $j$ 的最短路长度并且这条最短路的中间节点编号都 $\le k$。方法二把中间节点编号不超过 $k$推广为中间节点编号属于集合 $S$以便在子集之间做增量转移$f[S][i][j]$从 $i$ 到 $j$ 的最短路长度并且这条最短路的中间节点编号在集合 $S$ 中。状态转移方程假设已经算出了 $T$ 的 $f[T]$现在要计算 $S T \cup {k}$ 的 $f[S]$。节点 $k$ 带来的影响只有两种可能不影响 $i$ 到 $j$ 的最短路$f[S][i][j] f[T][i][j]$影响 $i$ 到 $j$ 的最短路即经过 $k$ 更短$f[S][i][j] f[T][i][k] f[T][k][j]$。二者取最小值得核心递推式$$ f[S][i][j] \min(f[T][i][j], f[T][i][k] f[T][k][j]) $$初始值与经典 Floyd 一致$$ f[\varnothing][i][j] g[i][j] $$即 $\textit{roads}$ 中 $i$ 到 $j$ 这条边的长度无边则为 $\infty$$g[i][i]0$。增量收益上述递推意味着每多算一个子集 $S$只需要 $\mathcal{O}(n^2)$ 的时间就可以得到该集合下任意点对的最短路——而方法一每个子集都要跑完整的 $\mathcal{O}(n^3)$ Floyd。这是两个方法时间复杂度的本质差距来源$n^3\cdot2^n$ vs $n^2\cdot2^n$。关键理解$S$ 是中间节点集合不是保留节点集合⚠️ 需要注意该计算过程不需要保证 $i$ 和 $j$ 都是 $S$ 中的元素$S$ 只是中间节点的编号集合不是保留的编号集合。但是如果设 $i$ 和 $j$ 都是 $S$ 中的元素那么从点 $i$ 到点 $j$、只经过 $S$ 中节点的情况下最短路长度恰好就是 $f[S][i][j]$。因此在「$i$ 和 $j$ 都是 $S$ 中的元素」的前提下$S$ 也可以直接当作当前保留的节点集合来用$f[S][i][j]$ 可以用来与 $\textit{maxDistance}$ 比较大小——这正是本题将子集最短路的增量计算与保留集合校验合二为一的关键。实现要点枚举 $S$ 时节点 $k$ 可以是 $S$ 中的任一元素比如最小元素或最大元素。各语言惯用取法Pythons.bit_length() - 1最高位、JavaInteger.numberOfTrailingZeros(s)与 C__builtin_ctz(s)与 Gobits.TrailingZeros(s)最低位。随后t s ^ (1 k)去掉 $k$ 得到 $T$即可从 $f[T]$ 递推 $f[S]$在计算 $f[S][i][j]$ 的同时可以同步检查「$i,j \in S$ 且 $f[S][i][j] \textit{maxDistance}$」一旦违反立刻把当前 $S$ 标记为不合法避免二次遍历由于 $f[S][i][j] f[S][j][i]$只需检查j i的一半点对$S\varnothing$即 $s0$必然满足条件没有保留任何节点或等价地保留节点间无需校验答案初始化为 1。参考实现Python3class Solution: def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) - int: g [[inf] * n for _ in range(n)] for x, y, wt in roads: g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) ans 1 # s0 一定满足要求 f [[[inf] * n for _ in range(n)] for _ in range(1 n)] f[0] g for s in range(1, 1 n): k s.bit_length() - 1 t s ^ (1 k) ok 1 for i in range(n): for j in range(n): f[s][i][j] min(f[t][i][j], f[t][i][k] f[t][k][j]) # 手动求 min 可以更快 if ok and j i and s i 1 and s j 1 and f[s][i][j] maxDistance: ok 0 ans ok return ansJavaclass Solution { public int numberOfSets(int n, int maxDistance, int[][] roads) { int[][] g new int[n][n]; for (int[] row : g) { Arrays.fill(row, Integer.MAX_VALUE / 2); } for (int[] e : roads) { int x e[0]; int y e[1]; int wt e[2]; g[x][y] Math.min(g[x][y], wt); g[y][x] Math.min(g[y][x], wt); } int ans 1; // s0 一定满足要求 int[][][] f new int[1 n][n][n]; for (int[][] matrix : f) { for (int[] row : matrix) { Arrays.fill(row, Integer.MAX_VALUE / 2); } } f[0] g; for (int s 1; s (1 n); s) { int k Integer.numberOfTrailingZeros(s); int t s ^ (1 k); boolean ok true; for (int i 0; i n; i) { for (int j 0; j n; j) { f[s][i][j] Math.min(f[t][i][j], f[t][i][k] f[t][k][j]); if (ok j i (s i 1) ! 0 (s j 1) ! 0 f[s][i][j] maxDistance) { ok false; } } } ans ok ? 1 : 0; } return ans; } }Cclass Solution { public: int numberOfSets(int n, int maxDistance, vectorvectorint roads) { vectorvectorint g(n, vectorint(n, INT_MAX / 2)); for (auto e: roads) { int x e[0], y e[1], wt e[2]; g[x][y] min(g[x][y], wt); g[y][x] min(g[y][x], wt); } int ans 1; // s0 一定满足要求 vectorvectorvectorint f(1 n, vectorvectorint(n, vectorint(n, INT_MAX / 2))); f[0] g; for (int s 1; s (1 n); s) { int k __builtin_ctz(s); int t s ^ (1 k); bool ok true; for (int i 0; i n; i) { for (int j 0; j n; j) { f[s][i][j] min(f[t][i][j], f[t][i][k] f[t][k][j]); if (ok j i (s i 1) (s j 1) f[s][i][j] maxDistance) { ok false; } } } ans ok; } return ans; } };Gofunc numberOfSets(n, maxDistance int, roads [][]int) int { g : make([][]int, n) for i : range g { g[i] make([]int, n) for j : range g[i] { g[i][j] math.MaxInt / 2 // 防止加法溢出 } } for _, e : range roads { x, y, wt : e[0], e[1], e[2] g[x][y] min(g[x][y], wt) g[y][x] min(g[y][x], wt) } ans : 1 // s0 一定满足要求 f : make([][][]int, 1n) for i : range f { f[i] make([][]int, n) for j : range f[i] { f[i][j] make([]int, n) for k : range f[i][j] { f[i][j][k] math.MaxInt / 2 } } } f[0] g for s : uint(1); s 1n; s { k : bits.TrailingZeros(s) t : s ^ (1 k) ok : true for i : 0; i n; i { for j : 0; j n; j { f[s][i][j] min(f[t][i][j], f[t][i][k]f[t][k][j]) if ok j i si1 ! 0 sj1 ! 0 f[s][i][j] maxDistance { ok false } } } if ok { ans } } return ans }复杂度分析时间复杂度$\mathcal{O}(m n^2\cdot 2^n)$其中 $m$ 为 $\textit{roads}$ 的长度。建图 $O(m)$每个子集仅用 $O(n^2)$ 从上一子集增量转移并同步校验共 $2^n$ 个子集。空间复杂度$\mathcal{O}(n^2\cdot 2^n)$需要为每个子集保存一张 $n\times n$ 的矩阵 $f[S]$。仓库实现佐证方法二正是仓库 d.go 中最终采用的numberOfSets实现第 9 行起。对比可发现初始化阶段显式保证g[i][i] 0注释g[i][i] 0也可以不加这个 if下面判断 maxDistance 时要保证 j ! i避免自环最短路干扰校验状态转移使用k : bits.TrailingZeros(s)选取 $S$ 的最小元素作为新增中转节点t : s ^ (1 k)得到去掉 $k$ 的 $T$递推式与文档完全一致校验与转移合并进同一双层循环ok一旦置 false 就不再比较短路同时利用j i只检查一半点对。此外模板库 copypasta/graph.go 的floydSubset约第 2060 行起把这一套路抽象成了可复用的模板函数注释明确标注了题目来源LC2959状态定义、bits.TrailingZeros(s)选 $k$、j i半矩阵校验等关键步骤与题解一一对应可以作为这类子集最短路题目的通用框架。测试验证仓库的自动化用例仓库为本题配置了完整的本地测试链测试入口 d_test.go通过testutil.RunLeetCodeFuncWithFile(t, numberOfSets, d.txt, targetCaseNum)读取 d.txt 中的用例并逐组断言targetCaseNum为 0 表示运行全部用例用例解析由 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile第 340 行起完成按每 $fNumIn fNumOut$ 行一组数据切分本题为 3 行输入 1 行输出再交给RunLeetCodeFuncWithExamples做反射调用、超时检测与输出比对。d.txt 中包含 3 组用例nmaxDistanceroads期望输出35[[0,1,2],[1,2,10],[0,2,10]]535[[0,1,20],[0,1,10],[1,2,2],[0,2,2]]7110[]2可以手动核对第一组3 个节点、阈值 5任意两节点之间要么直接相邻$0$-$1$ 长 2要么经 1 中转$0$-$2$ 长 12、$1$-$2$ 长 10 均超阈值因此只有 $\varnothing$、三个单点集以及 ${0,1}$ 共 5 种方案。最后一组 $n1$、无边空集与单点集各算一种答案恰为 2验证了$s0$ 一定满足要求、答案从 1 起算的初始化逻辑。若想本地复现在该仓库目录下运行go test ./leetcode/biweekly/119/d -run Test_d -v测试所需依赖见仓库根目录的 go.mod。同类题目与延伸练习本题融合了全源最短路Floyd与二进制枚举/状压两条知识线文档末尾给出了对应的练习清单可依难度循序渐进Floyd 相关题号后的数字为难度分设计可以求最短路径的图类1811动态加边的 Floyd与模板库floydShortestPath中addEdge注释见 copypasta/graph.go 第 2003 行附近对应阈值距离内邻居最少的城市1855Floyd 后统计阈值内邻居数是理解本题校验环节的入门题转换字符串的最小成本 I1882与 2977. 转换字符串的最小成本 II2696Floyd 与 DP 的进一步组合。二进制枚举相关子集、77. 组合枚举集合的基础功字母组合迭代器1591、2397. 被列覆盖的最多行数1719、2212. 射箭比赛中的最大得分1869基于陈述统计最多好人数1980、1601. 最多可达成的换楼请求数目2119、1617. 统计子树中城市之间最大距离2309——后几题已接近本题的枚举 图结构校验组合难度。模板库 copypasta/graph.go 中与该题直接相关的还有位压缩版 FloydfloydBitset第 2032 行起把布尔可达性压缩进Bitset单次或运算合并整行可达点复杂度 $\mathcal{O}(n^3/w)$$w$ 为机器字长适用于传递闭包类问题标准 FloydfloydShortestPath第 1965 行起含动态加边、负环检测、稀疏图剪枝等通用扩展。小结本题的两种解法恰好展示了枚举所有子集这一类问题的两条优化路径方法一二进制枚举 Floyd思路直接、实现简单每个子集独立跑最短路代价是 $\mathcal{O}(n^3\cdot2^n)$ 的总复杂度适合 $n$ 较小的场景方法二状压 DP Floyd把 Floyd 的三维状态从编号前缀推广为节点集合利用子集间的增量递推把每个子集的最短路计算降为 $\mathcal{O}(n^2)$总复杂度 $\mathcal{O}(n^2\cdot2^n)$以 $\mathcal{O}(n^2\cdot2^n)$ 空间换取时间。关键要点可总结为三条预处理邻接矩阵避免重复建图牢记$S$ 是中间节点集合、仅在 $i,j\in S$ 时作为保留集合校验这一状态语义利用 $f[S][i][j]f[S][j][i]$ 的对称性只校验j i的一半点对。仓库中 d.go 的两种实现、copypasta/graph.go 的floydSubset模板以及 d.txt 的测试用例可以作为你复现与扩展这套思路的可靠参照。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐3步掌握模块化游戏模组管理开源Mod Loader完全指南3步掌握模块化游戏模组管理开源Mod Loader完全指南 Mod Loader是一款专为《侠盗猎车手》III、罪恶都市和圣安地列斯设计的革命性模组管理工具游戏开发单调队列优化 DP 实战LeetCode 2945「找到最大非递减数组的长度」——codeforces-go 题解深度解析单调队列优化 DP 实战LeetCode 2945「找到最大非递减数组的长度」——codeforces go 题解深度解析 本篇技术指南以 LeetCode科学计算解锁codeforces-go从入门到精通的区间DP与环形DP实战指南解锁codeforces go从入门到精通的区间DP与环形DP实战指南 在算法竞赛的世界里动态规划DP是解决复杂问题的核心武器之一。而codeforce科学计算上一篇5 步生成可用的 OpenCore EFI黑苹果工具 OpCore-Simplify 完整实操指南下一篇终极Windows窗口调整神器3分钟学会强制修改任意窗口大小创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
