tkdsheep-ZOJ2342

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

shi哥解题报告里极力推荐的一道题，确实非常巧妙

得出  L石头路+L烂泥路>=C石头路-C烂泥路 这个不等式并不难，应该人人都能推出来 （L代表修改了多少)
现在要使sum(L)尽可能小，解题报告里说可以转化为二分图最佳匹配(KM算法)，但我始终想不明白这跟最佳匹配有什么关系。。

后来又看了mj和其他人的解题报告，才明白，原来KM算法的过程中，会对每个点维护一个顶标，对于二分图中的任意一条边，两个端点的顶标之和都大于等于这个边权值，同时做完最佳匹配之后，所有点的顶标和是最小的，于是恰好满足本题的两个约数条件

这就跟ZOJ2318判负环利用了最短路spfa一样，本身不需要最短路，只是利用最短路算法判断了负环而已，看来只会模板确实是硬伤，如果不了解算法的具体实现过程，遇到这种很巧妙的问题就无从下手了

仰慕shi哥、mj

shi哥解题报告里极力推荐的一道题，确实非常巧妙

得出 L石头路+L烂泥路>=C石头路-C烂泥路 这个不等式并不难，应该人人都能推出来 （L代表修改了多少)

现在要使sum(L)尽可能小，解题报告里说可以转化为二分图最佳匹配(KM算法)，但我始终想不明白这跟最佳匹配有什么关系。。

后来又看了mj和其他人的解题报告，才明白，原来KM算法的过程中，会对每个点维护一个顶标，对于二分图中的任意一条边，两个端点的顶标之和都大于等于这个边权值，同时做完最佳匹配之后，所有点的顶标和是最小的，于是恰好满足本题的两个约数条件

这就跟ZOJ2318判负环利用了最短路spfa一样，本身不需要最短路，只是利用最短路算法判断了负环而已，看来只会模板确实是硬伤，如果不了解算法的具体实现过程，遇到这种很巧妙的问题就无从下手了

仰慕shi哥、mj