二分图之|二分图之多重匹配和最大权匹配等总结二分图之多重匹配和最大权匹

一.多重匹配：
HDU3605 Escape （裸题） POJ2289 Jamie's Contact Groups（二分+多重匹配） POJ3189 Steady Cow Assignment（二分+多重匹配） POJ2112 Optimal Milking（二分+多重匹配）

二.最大权匹配及KM算法：
模板：

文章图片

文章图片

1 bool DFS(int x) //找增广路 2 { 3visx[x] = true; 4for(int y = 1; y<=ny; y++) 5{ 6if(visy[y]) continue; 7int tmp = lx[x] + ly[y] - g[x][y]; 8if(tmp==0)//遇到可匹配的，尝试找增广路 9{ 10visy[y] = true; 11if(linker[y]==-1 || DFS(linker[y])) 12{ 13linker[y] = x; 14return true; 15} 16} 17else//否则，更新最小期望差值 18slack[y] = min(slack[y], tmp); 19} 20return false; 21 } 22 23 int KM() 24 { 25memset(linker, -1, sizeof(linker)); 26memset(ly, 0, sizeof(ly)); //初始化右边标杆 27for(int i = 1; i<=nx; i++)//初始化左边标杆 28{ 29lx[i] = -INF; 30for(int j = 1; j<=ny; j++) 31lx[i] = max(lx[i], g[i][j]); 32} 33 34for(int x = 1; x<=nx; x++)//为左边的每个点找到匹配对象 35{ 36for(int i = 1; i<=ny; i++)//初始化最小期望差值 37slack[i] = INF; 38while(true)//多次调整标杆（其实就是多次降低期望值，降低最大权值和），直到找到增广路 39{ 40memset(visx, 0, sizeof(visx)); 41memset(visy, 0, sizeof(visy)); 42 43if(DFS(x)) break; //找增广路，如果找不到，则需要继续降低期望值。 44int d = INF; 45for(int i = 1; i<=ny; i++) 46if(!visy[i]) 47d = min(d, slack[i]); 48 49for(int i = 1; i<=nx; i++)//左边访问过的降低期望值，从而可以与未尝试过的点尝试匹配。 50if(visx[i]) 51lx[i] -= d; 52for(int i = 1; i<=ny; i++)//右边访问过的提高期望值，以平衡左边减去的那部分。 53{ 54if(visy[i]) ly[i] += d; 55else slack[i] -= d; 56} 57} 58} 59 60int res = 0; 61for(int i = 1; i<=ny; i++) 62if(linker[i]!=-1) 63res += g[linker[i]][i]; 64return res; 65 }

View Code 对KM算法的理解：
假设左边的点为男生，右边的点为女生。为每个男生都找到女朋友，且好感度之和要最大。
1.在开始下手之前，每个男生心目中都有一个最喜欢的女生，即好感度最高的。于是，我们就把男生的初始期望值设置为好感度最高的，以表明他们都想得到他们最喜欢的女生。人嘛，一开始都是想要最好的。在这里，初始最大权值和即为所有男生的期望值之和。
2.现在开始找女朋友了：从左边挑选一个没有找到女朋友的男生开始，逐个女生地挑：
1)如果不是自己期望值最高的那个女生，那就先不向她示意，而是把她作为保留选择（人都这样），同时，这个男生需要更新一下：如果被最期望值最高的女生拒绝，则最少需要降低多少期望值，才可以继续找女朋友，且是剩下的期望值最高的（人嘛，受挫了就要降低姿态。但是又仍然保留了那份高傲，即使降低姿态也不能降太低）。
2)如果是自己期望值最高的女生，还等什么，赶紧下手啊！如果女生没有男朋友，或者女生的男朋友可以找到另外一个女生做女朋友（不是自己的永远是最好的）
则成功啦！！然而，如果女生的男朋友找不到另外一个女生做女朋友，那人家肯定不能拱手让爱吧？？所以就失败了，那怎么办？女朋友还是要找的，日子还是要过的。所以男生啊，事实哪有想象中的那么美好。所以只能降低一下期值，然后继续找，不言弃，直至成功！！（写代码的时候是访问过的男生都降低最小的期望差值，访问过的女生都增加最少的期望差值，这样左边减少的转移到右边去了，但又因为最大权值和设得过高了，所以左边部分减少的肯定多于右边部分增加的。）
HDU2255 奔小康赚大钱（裸题） HDU3488 Tour（深入理解KM算法） UVA11383 Golden Tiger Claw（KM算法的性质） Uvalive 4043 Ants（KM算法的利用）

三.婚姻稳定问题 Gale - Shapely算法：
UVALive3989 Ladies' Choice 【二分图之|二分图之多重匹配和最大权匹配等总结】
转载于:https://www.cnblogs.com/DOLFAMINGO/p/7852316.html