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”