网络流——二分图最优匹配KM算法

前言

其实这个东西只是为了把网络流的内容凑齐而写的(反正我是没有看到过这样子的字体不知道田忌赛马算不算

算法过程

我们令左边的点(其实二分图没有什么左右)为女生,右边的点为男生,那么:

  1. 为每一个女生定一个心仪值,心仪值为她与男生连边中的最大值
  2. 为每一个女生找对象,要求男生的心仪值和女生的心仪值的和为他们的边权(男生的心仪值初始为0真惨
  3. 如果没有找到对象,那么将2过程中的女生的心仪值全部-Min,男生的心仪值全部+Min(这个Min是通过自己算的,就是女生除了之前或当前心仪的男生外最心仪的男生的心仪值与她的心仪值之和减去边权的值)
  4. 重新为她找对象,直到找到或者当前女生的心仪值为0。

以上就是KM的基本过程,虽然看上去比较麻烦,但是实现上也很麻烦……

代码实现(略)

原文地址:https://www.cnblogs.com/cj-gjh/p/10256346.html

时间: 01-11

网络流——二分图最优匹配KM算法的相关文章

poj 2195 Going Home 二分图最小权匹配KM算法

题意: 有n个人要回到n间房子里,每间房子只允许一个人,求n个人要走的最小距离和. 分析: 裸的二分图最小权匹配,KM搞之. 代码: //poj 2195 //sep9 #include <iostream> using namespace std; const int maxN=128; char g[maxN][maxN]; int mx[maxN],my[maxN],hx[maxN],hy[maxN]; int w[maxN][maxN]; int lx[maxN],ly[maxN],l

HDU_2255 二分图最佳完美匹配 KM匈牙利算法

一开始还没看懂这个算法,后来看了陶叔去年的PPT的实例演示才弄懂 用一个lx[]和ly[]来记录X和Y集合中点的权值,有个定理是 lx[i]+ly[j]==w[i][j](边权值) 则该点是最佳匹配,因为首先 那个不等式肯定要>=的,否则就不满足题意了,如果是>则可以去匹配更有价值的边或者把权值降下来让匹配边的潜力更大. 所以只有把握了这个条件,其他就是走一遍最大匹配数.以及up()函数用来在无法匹配的时候,进行其他点的权值降低(也可以说是增广路的搜索)来得到匹配. #include <

POJ 2195 Going Home【最小费用流 二分图最优匹配】

题目大意:一个n*m的地图,上面有一些人man(m)和数量相等的house(H) 图上的距离为曼哈顿距离 问所有人住进一所房子(当然一个人住一间咯)距离之和最短是多少? 思路:一个人一间房,明显是二分图的模型,边权为人和房子的曼哈顿距离,然后算一下最小距离即可 懒得学KM了 最小费用流的经典建图 #include #include #include #include #include #define maxn 40000 #define inf 0x3f3f3f3f using namespac

hdu2255 奔小康赚大钱 二分图最佳匹配--KM算法

传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子.这可是一件大事,关系到人民的住房问题啊.村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子.另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(

ACM学习历程—POJ3565 Ants(最佳匹配KM算法)

Young naturalist Bill studies ants in school. His ants feed on plant-louses that live on apple trees. Each ant colony needs its own apple tree to feed itself. Bill has a map with coordinates of n ant colonies and n apple trees. He knows that ants tra

LA4043 - Ants(二分图完备最佳匹配KM)

option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044 大致题意: 平面上有n个白点和n个黑点,求一种完美匹配使他们间的连线不相交 思路:要注意到,若有两种匹

hdu1853 Cyclic Tour (二分图匹配KM)

Cyclic Tour Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/65535 K (Java/Others)Total Submission(s): 1688    Accepted Submission(s): 859 Problem Description There are N cities in our country, and M one-way roads connecting them. Now Li

hdu2255 奔小康赚大钱,最大权匹配,KM算法

点击打开链接 最大权匹配 KM算法 算法步骤: 设顶点Xi的顶标为a[i],顶点Yi的顶标为b[i] ⅰ.初始时,a[i]为与Xi相关联的边的最大权值,b[j]=0,保证a[i]+b[j]>=w(i,j)成立 ⅱ.当相等子图中不包含完备匹配时,就适当修改顶标以扩大相等子图,直到找到完备匹配为止 ⅲ.修改顶标的方法 当从Xi寻找交错路失败后,得到一棵交错树,它的所有叶子节点都是X节点,对交错树中X顶点的顶标减少d值,Y顶点的顶标增加d值,对于图中所有的边(i,j), 可以看到: i和j都不在交错树

KM算法详解[转]

KM算法详解 原帖链接:http://www.cnblogs.com/zpfbuaa/p/7218607.html#_label0 阅读目录 二分图博客推荐 匈牙利算法步骤 匈牙利算法博客推荐 KM算法步骤 KM算法标杆(又名顶标)的引入 KM流程详解 KM算法博客推荐 0.二分图 二分图的概念 二分图又称作二部图,是图论中的一种特殊模型. 设G=(V, E)是一个无向图.如果顶点集V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在X中,另一个在Y中,则称图G为二分图. 可以

KM算法(二分图的最佳完美匹配)

网上一堆人写KM算法,还没搜出哪个讲得比较好的. KM算法大概过程: (1)初始化Lx数组为该boy的一条权值最大的出边.初始化Ly数组为 0. (2)对于每个boy,用DFS为其找到一个girl对象,顺路记录下S和T集,并更新每个girl的slack值.若不能为其找到对象,则转3. (3)找出非T集合的girl的最小slack值为d,更新S集中的boy和T集中的girl,并且顺路更新非T集中的slack值.对于那个失败的boy继续第2步. 简括之,就是在保持当前权和最高的情况下,尽量为每个bo