二分图的最佳匹配 KM 算法

逃离我推掉我的手 2022-03-18 15:24 228阅读 0赞

KM算法求最小权二分匹配，模板题，构图很简单，直接把人当作左边的点，房子当作右边的点，  
两者之间的曼哈顿距离当作权值即可。第一次搞带权二分匹配的题，就是用KM算法求最小权的时候要加个处，由于KM求的是最大权，  
所以在套模板之前把权值都取下相反值最后再把KM算法求出来的最大权值取反即可。  
  
  
Kuhn－Munkras算法流程：  
　　(1)初始化可行顶标的值  
　　(2)用匈牙利算法寻找完备匹配  
　　(3)若未找到完备匹配则修改可行顶标的值  
　　(4)重复(2)(3)直到找到相等子图的完备匹配为止  
  
  
引用：  
KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A\[i\]，顶点Yi的顶标为B \[i\]，顶点Xi与Yj之间的边权为w\[i,j\]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A\[i\]+B\[j\]>=w\[i,j\]始终 成立。KM算法的正确性基于以下定理：  
　　若由二分图中所有满足A\[i\]+B\[j\]=w\[i,j\]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。  
　　这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。  
　　初始时为了使A\[i\]+B\[j\]>=w\[i,j\]恒成立，令A\[i\]为所有与顶点Xi关联的边的最大权，B\[j\]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。  
　　我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：  
两端都在交错树中的边(i,j)，A\[i\]+B\[j\]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。  
两端都不在交错树中的边(i,j)，A\[i\]和B\[j\]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。  
X端不在交错树中，Y端在交错树中的边(i,j)，它的A\[i\]+B\[j\]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。  
X端在交错树中，Y端不在交错树中的边(i,j)，它的A\[i\]+B\[j\]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。  
　　现在的问题就是求d值了。为了使A\[i\]+B\[j\]>=w\[i,j\]始终成立，且至少有一条边进入相等子图，d应该等于min\{A\[i\]+B\[j\]-w\[i,j\]|Xi在交错树中，Yi不在交错树中\}。  
　　以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶 标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数 slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack\[j\]变成原值与A \[i\]+B\[j\]-w\[i,j\]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改 顶标后，要把所有的slack值都减去d。  
  
  
\#include <cstdio>  
\#include <memory.h>  
\#include <algorithm> // 使用其中的 min 函数  
using namespace std;  
  
  
const int MAX = 1024;  
  
  
int n; // X 的大小  
int weight \[MAX\] \[MAX\]; // X 到 Y 的映射（权重）  
int lx \[MAX\], ly \[MAX\]; // 标号  
bool sx \[MAX\], sy \[MAX\]; // 是否被搜索过  
int match \[MAX\]; // Y(i) 与 X(match \[i\]) 匹配  
  
  
// 初始化权重  
void init (int size);  
// 从 X(u) 寻找增广道路，找到则返回 true  
bool path (int u);  
// 参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配  
int bestmatch (bool maxsum = true);  
  
  
void init (int size)  
\{  
// 根据实际情况，添加代码以初始化  
n = size;  
for (int i = 0; i < n; i ++)  
for (int j = 0; j < n; j ++)  
scanf ("%d", &weight \[i\] \[j\]);  
\}  
  
  
  
  
bool path (int u)  
\{  
sx \[u\] = true;  
for (int v = 0; v < n; v ++)  
if (!sy \[v\] && lx\[u\] + ly \[v\] == weight \[u\] \[v\])  
\{  
sy \[v\] = true;  
if (match \[v\] == -1 || path (match \[v\]))  
\{  
match \[v\] = u;  
return true;  
\}  
\}  
return false;  
\}  
  
  
int bestmatch (bool maxsum)  
\{  
int i, j;  
if (!maxsum)  
\{  
for (i = 0; i < n; i ++)  
for (j = 0; j < n; j ++)  
weight \[i\] \[j\] = -weight \[i\] \[j\];  
\}  
  
  
// 初始化标号  
for (i = 0; i < n; i ++)  
\{  
lx \[i\] = -0x1FFFFFFF;  
ly \[i\] = 0;  
for (j = 0; j < n; j ++)  
if (lx \[i\] < weight \[i\] \[j\])  
lx \[i\] = weight \[i\] \[j\];  
\}  
  
  
memset (match, -1, sizeof (match));  
for (int u = 0; u < n; u ++)  
while (1)  
\{  
memset (sx, 0, sizeof (sx));  
memset (sy, 0, sizeof (sy));  
if (path (u))  
break;  
  
  
// 修改标号  
int dx = 0x7FFFFFFF;  
for (i = 0; i < n; i ++)  
if (sx \[i\])  
for (j = 0; j < n; j ++)  
if(!sy \[j\])  
dx = min (lx\[i\] + ly \[j\] - weight \[i\] \[j\], dx);  
for (i = 0; i < n; i ++)  
\{  
if (sx \[i\])  
lx \[i\] -= dx;  
if (sy \[i\])  
ly \[i\] += dx;  
\}  
\}  
  
  
int sum = 0;  
for (i = 0; i < n; i ++)  
sum += weight \[match \[i\]\] \[i\];  
  
  
if (!maxsum)  
\{  
sum = -sum;  
for (i = 0; i < n; i ++)  
for (j = 0; j < n; j ++)  
weight \[i\] \[j\] = -weight \[i\] \[j\]; // 如果需要保持 weight \[ \] \[ \] 原来的值，这里需要将其还原  
\}  
return sum;  
\}  
  
  
  
  
int main()  
\{  
int n;  
scanf ("%d", &n);  
init (n);  
int cost = bestmatch (true);  
  
  
printf ("%d ", cost);  
for (int i = 0; i < n; i ++)  
\{  
printf ("Y %d -> X %d ", i, match \[i\]);  
\}  
  
  
return 0;  
\}  
  
  
/\*  
5  
3 4 6 4 9  
6 4 5 3 8  
7 5 3 4 2  
6 3 2 2 5  
8 4 5 4 7  
//执行bestmatch (true) ，结果为 29  
\*/  
  
  
/\*  
5  
7 6 4 6 1  
4 6 5 7 2  
3 5 7 6 8  
4 7 8 8 5  
2 6 5 6 3  
//执行 bestmatch (false) ，结果为 21  
\*/

这个实现和图论书上描述的有所不同，这个和匈牙利算法方法上是一样的（不断地寻找增广道路。。），而不是像书上在过程中调用匈牙利算法。。

一个实例:

## Description ##

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，效率会大大提高。因此，百度决定进行一次员工座位的大调整。 调整的方法如下： 1．首先将办公区按照各种零食的摆放分成N个不同的区域（例如：可乐区，饼干区，牛奶区等等）； 2．每个员工对不同的零食区域有不同的喜好程度（喜好程度是1~100的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）； 3．由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案使得总的喜好程度最大。

## Input ##

第一行包含两个整数N，M(N>=1，M<=300)。分别表示N个区域和M个员工； 第二行是N个整数构成的数列a，其中a[i]表示第i个区域可以容纳的员工数(1<=a[i]<=M，a[1]+a[2]+...+a[N]=M)； 紧接着是一个M*N的矩阵P，P(i,j)表示第i个员工对第j个区域的喜好程度.

## Output ##

对于每个测试数据，输出可以达到的最大的喜好程度。

## Sample Input ##

3 3 1 1 1 100 50 25 100 50 25 100 50 25

## Sample Output ##

175

## Hint ##

此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为100+50+25=175

## Source ##

Astar2006 初赛

做法就是KM算法

我的建图过程如下： 把食品供应点拆开，不要让他成为一个点，如果一个食品供应点能够供应2个人，那就把它拆开成两个点，由于食品供应点的所有人数之和是等于员工数的，所以刚好构成一个两边点数一样的一个二分图，然后从员工到供应点连边的边权就是喜好度，然后再用KM算法进行最大带权匹配就好了，最后建的图是一个M*M的矩阵，由于M小于300，所以KM算法能够过。

也见到过别人用DP过掉的，不过没有想通。。DP一直很弱。。

话说我已经退役了，这个博客很少用了。。

#include<stdio.h>   
          #include<algorithm>   
          #include<string.h>   
          #define inf 99999999   
          #define maxn 305   
             
          using namespace std;   
             
          int n,m;   
          int a[maxn];   
          int map[maxn][maxn];   
          int temp[maxn][maxn];   
          int link[maxn];   
          int lx[maxn],ly[maxn];   
          bool x[maxn],y[maxn];   
             
             
          bool dfs(int u)   
          {   
              int i;   
              x[u]=true;   
              for(i=1;i<=n;i++)   
              {   
                  if(lx[u]+ly[i]==map[u][i]&&!y[i])   
                  {   
                      y[i]=true;   
                      if(link[i]==-1||dfs(link[i]))   
                      {   
                          link[i]=u;   
                          return true;   
                      }   
                  }   
              }   
              return false;   
          }   
             
          int main()   
          {   
              int i,j,k,num;   
              while(scanf("%d%d",&m,&n)!=EOF)   
              {   
                  for(i=1;i<=m;i++)   
                      scanf("%d",&a[i]);   
                  for(i=1;i<=n;i++)   
                      for(j=1;j<=m;j++)   
                          scanf("%d",&temp[i][j]);   
                  for(i=1;i<=n;i++)   
                  {   
                      num=0;   
                      for(j=1;j<=m;j++)   
                      {   
                          for(k=1;k<=a[j];k++)   
                          {   
                              num++;   
                              map[i][num]=temp[i][j];   
                          }   
                      }   
                  }   
                  memset(x,0,sizeof(x));   
                  memset(y,0,sizeof(y));   
                  memset(link,-1,sizeof(link));   
                  memset(ly,0,sizeof(ly));   
                  for(i=0;i<maxn;i++)   
                      lx[i]=inf;   
                  for(k=1;k<=n;k++)   
                  {   
                      while(1)   
                      {   
                          memset(x,0,sizeof(x));   
                          memset(y,0,sizeof(y));   
                          if(dfs(k))   
                              break;   
                          int d=inf;   
                          for(i=1;i<=n;i++)   
                              if(x[i])   
                                  for(j=1;j<=n;j++)   
                                      if(!y[j]&&lx[i]+ly[j]-map[i][j]<d)   
                                          d=lx[i]+ly[j]-map[i][j];   
                          for(i=1;i<=n;i++)   
                              if(x[i])   
                                  lx[i]=lx[i]-d;   
                          for(i=1;i<=n;i++)   
                              if(y[i])   
                                  ly[i]=ly[i]+d;   
                      }   
                  }   
                  int ans1=0,ans2=0;   
                  for(i=1;i<=n;i++)   
                      ans1=ans1+map[link[i]][i];   
                  printf("%d\n",ans1);   
              }   
              return 0;   
          }

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow]

[https_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485