UOJ 无限 waiting 的解决方法
本文讲的是自己搭建的 UOJ 如何解决无限 waiting，而不是 http://uoj.ac 如何解决无限 waiting（后者大概要联系 vfk..反正我是没遇到过）。
「NOI2014」购票（斜率优化，点分治）
2019，以及毕业之前
怀着伤感的心情写下这段文字，然后开始一段新的征程。
悬崖边的踟蹰 —— CSP-S 2019
标题来自 三月のライオン Chapter.64 銀の羽根 ：
答案只在漆黑的水底。
越是前进，下一个答案就只能在更深的地方找到。
以前越是潜入，就能获得答案。
比起恐怖，欲望更胜一筹。
但是成为职业棋手 6 年后，如今变得完全不能前进。
即便带着要撕碎全身的想法去潜入，但是却空手而回，已经是很常见的事了。
比起 「也许能找到」，「反正又不一定能找到」这个念头胜利的时候，就只能进行有限的努力了。
但是，桐山和二海堂无视了那样的我。
理所当然一样无论多少次都跳入其中。根本就不正常。
他们即便屡次空手而归，也会制定对策继续挑战。
丝毫不介意痛苦，无论多少次都投身其中。
只留下，被恐惧压倒的我。
基于 Capacity Scaling 的弱多项式复杂度最小费用流算法
大多数人所使用的费用流算法，即每次求出残量网络中 $s$ 到 $t$ 关于费用的最短路进行增广（将 Dinic 最大流算法中的 BFS 改为 SPFA），是伪多项式复杂度的，最坏情况下复杂度为 $O(nmf)$，其中 $f$ 为最大流。已知有一种在点数为 $n$，边数为 $O(n^2)$，值域为 $O(2^{n/2})$ 时将其用时卡成关于 $n$ 的指数级复杂度的构造方法。
本文将介绍一种复杂度为进行 $O(m\log U)$ 次（$U$ 表示边的最大容量）无负权边单源最短路（使用 priority_queue 实现 Dijkstra 算法，总复杂度即为 $O(m^2\log U\log m)$）的弱多项式复杂度算法。
其实这个算法并不是很复杂（只是相关资料比较少，会对学习造成一定困难，这也是我写这篇博客的原因），最小费用最大流的模板也只需要 $2.5KB$，并不比常见的伪多项式复杂度算法长很多。