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

一.多重匹配：

HDU3605 Escape （裸题）

POJ2289 Jamie's Contact Groups（二分+多重匹配）

POJ3189 Steady Cow Assignment（二分+多重匹配）

POJ2112 Optimal Milking（二分+多重匹配）

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

模板：

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

View Code

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