标签： KM算法

https://cn.vjudge.net/problem/SGU-206

这个题乍一看不可做系列(难道不是吗)，像是跟生成树相关的问题。然而看了dalao的博客和论文之后总算搞明白了原来要转化为二分图模型。而之所以能转化就是因为里面的绝对值去掉不等式（去绝对值用的是贪心的思想，1-n-1之间的都要变小，n到m的都要变大）之后，非树边 j 和树边 i 的delta关系可以写成Di+Dj>=Ci-Cj,然后dalao们就想到了KM算法里的标杆与权值之间的不等式关系 鬼知道他们怎么想到的 继续阅读“[二分图带权匹配][KM算法][图论][模型转化] SGU 206 Roads”

为什么模板题都a的这么艰难

调了这么久发现其实原来的就是对的只是样例可以有不同解，蠢的程度也是没谁了。。。

题意就是求DAG上的最小路径覆盖数，而且使得所有路径权值之和最小，而且要输出路径。将每一个点拆成两个点，分别在二分图左右两侧，读入的所有的路都是从左往右。   求最小路径覆盖也就是求最大匹配，而在这一条件下要求总长度最小，将边附上权值求最小权最大匹配即可。由于KM算法 继续阅读“[带权二分图][KM算法][模板] SGU252 Railway Communication”