Peanut-Tang

突然在 U 群里爆出了这题，回想起了这道当时自己感觉挺有趣的一题，过来写篇题解。

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

有效电阻是电磁学电路问题中的基本概念，在图论中亦有这重要地位。

一种可以在 $O(m\log |f| (m + n) \log m)$ 时间复杂度内求解最大流的诡异方法，其中 $|f|$ 是最大流流量。方法名称是我自己胡乱翻译的，原名叫：The Fattest Augmenting Path Heuristic。

布谷鸟哈希学习笔记。

论文 On the All-pairs-shortest-path Problem. Raimund Seidel, 1992 阅读笔记。这篇文章给出了一个在 $O(M(n)\log n)$ 时间复杂度内计算出无向无权图全源最短路长度的算法，和一个在 $O(M(n)\log n)$ 时间复杂度内找出全源最短路的随机算法，其中 $M(n)$ 为对两个 $n\times n$ 的小整数矩阵做乘法的时间复杂度（注意：如果有 $M(n)=O(n^2)$，则找出全源最短路时间复杂度为 $O(n^2\log^2 n)$）。该算法还可以推广到有向无权图上。

最大流最小割的优化证明。

这是一道很多微积分教材上都有的拉格朗日乘子法例题。但令笔者十分不满意的是，大部分教材直接给出了 $V(x,y,z)=8xyz$ 这样一个体积表达式，却没有给出为什么。明明长方体的边可以不平行于坐标轴。近日笔者认真思考了这一问题，得到了完备的证明，自觉这个解答有些有趣，故在此记录。

希尔排序，思想简单，代码容易，但内核丰富，时间复杂度证明富含数学知识，在此记录。