JustPureH₂O

在写 SPFA 判负环 的时候发现很多题目需要联系到高贵的0/1分数规划，但是截至当时我还没有学这样优雅的算法，故先将 \texttt{SPFA} 咕一咕，把关于分数规划的东西弄清楚再回去填坑。正好刚考完高一下的合格考，觉得正是适合学新东西的时候，在此归纳一些简单的分数规划知识……这都什么跟什么啊

我非常喜欢一些奇技淫巧，每次有机会时就想用点小技巧，既方便了自己、有时还能博来他人的赞叹，实属一举两得的行为。在这篇文章之前，我的奇技淫巧仅局限于高中数学题。接下来我把进入 C++ 编程以来收集的实用小技巧全部放在这里，并不定时更新新的小技巧。希望能帮到后人。

生成树，在 OI 中最多的考法有两种——最小生成树和次小生成树。最小生成树（Minimum Spanning Tree，MST）是最常见的问题，它是原图边权之和最小的生成树（不一定唯一）；而次小生成树，分为严格次小生成树和非严格次小生成树，前者要求次小生成树的权值和严格小于最小生成树的权值和，后者则无此要求，即允许“大于等于”情况的出现。实际考察严格次小生成树较多。

又名：端午游寄——三傻大闹写字楼归还充电宝传奇

Floyd 算法是一种能在 \mathcal O(n^3) 时间复杂度内求出任意两点间最短路长度的多源最短路算法，又称 \texttt{Floyd-Warshall} 算法或插点法，以它的发明者命名。Floyd 算法基于动态规划，通过穷举 i 节点和 j 节点的所有中继节点 k 进行松弛操作得到最短路径。对于稠密图，它的执行效率会快于 Dijkstra 和 Bellman-Ford 算法。

行列式最初作为判断某个方程组是否有解的依据被人们使用，记作 \det，有时也用形如 \left|\begin{matrix}a_1&a_2&a_3\\b_1&b_2&b_3\\c_1&c_2&c_3\end{matrix}\right| 的式子来表示这个矩阵的行列式的值。类比一元二次方程的 \Delta 判别式——我们定义，当矩阵 A 的行列式的值为零时，该矩阵方程组无解，即 \det(A)=0 时方程组无解。

我们先前在 这篇文章 中探讨了 A* 算法以及其实现思路。回顾一下，A* 算法为普通的搜索算法加上了一个名为估价函数的设置，使得 A* 能够在搜索时不会那么偏离正确答案（最短路径）。从而大幅改善了普通 BFS 的近似穷举的低效策略。

试看如下例题：