Taxi

套路题又来咯，最大值最小先直接上个二分答案\(lim\) 对于图中的边，若它的权值\(>lim\)的话这条边的方向就确定了，那么直接把这些边连出来跑个拓扑排序看看有没有环即可 如果有环则当前答案一定不合法，否则我们总存在如下的构造方法： 先把权值\(>lim\)的边得到的图的拓扑序搞出来，对于所有权 ......

这道题很恶心，终于想通了…… 首先是考场做法，先模拟一下样例，猜结论。 首先直觉上告诉我们：一定要尽量让牛在车上，不要空车，也就是只有到了有牛的地方或者终点才会让牛进行上车、下车的操作。 然后就是车肯定至少要开牛的路程之和，然后让多出来的那部分最小。 根据这个样例模拟一下最优解和非最优解，发现多出来 ......

删边最短路 这篇题解的特点 其实其他的题解都有几处证明跳跃的点。比如，怎么证明删边最短路只强制经过一条边就足够，而不需要强制经过两条，三条边呢？这个结论的证明并不如想象中简单，而且我想读者阅读完其它题解后也很难意识到这个结论只在 无向正权图 上成立，只要负权 / 零权 / 有向，这个结论就立刻失效了 ......