HDU 2853 Assignment

By NodeKey in ACM on 13 Aug 2016

最近在水KM算法 只要把KM理解了 至今写到的大部分都是水题 唯独这题让我写了很长时间 看了其他人的博客才明白什么叫建图的巧妙和重要性 题意 有n家公司和m个任务 所有任务和公司都已经匹配好了 要求在尽量保留原有匹配的基础上 求得最优匹配 输出改变的数量 和 改变后增加的权值 巧妙的思路来了 首先对于所有输入的权值增大K倍 这里的K必须大于n 再对原匹配的权值都加 1 这样 原匹配的优先级将大于其他匹配 再套模板 这时出来的结果 将是匹配权值数的K倍再加上原匹配的数目 （所以这里就体现了K大于n的原因了 若是K小于n 那么大于K的部分将可能成为原匹配数目，结果将乱套……………… AC Code #include #include #include #include #include #include using namespace std; const int maxn=55; const int inf=0x3f3f3f3f; int cn…

KM 算法学习

By NodeKey in ACM on 11 Aug 2016

KM算法 用于求二分图的最佳完美匹配 即权值最大的完美匹配 如果你也是个刚来学习KM算法的人 大概的用途肯定还是知道的吧 还是直接说重点吧 首先 理解KM算法前 必须有以下3个概念 1.可行顶标 对于一个赋值二分图G(x,y,e,w) (x,y 代表二分图的两边顶点标号 e代表边 w代表边的权值 ) 我们对两边的每一个顶点都赋予一个额外的值 使得对于二分图G内的所有边 e=xy 均有 lx(x)+ly(y)>=w(xy) 其实不管什么样的图 什么样的边权 可行顶标必然存在 例如 lx(x)=max w(xy) ly(y)=0 2.在已经赋值可行顶标的二分图中 保留所有lx(x)+ly(y)…