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步。

　　简括之，就是在保持当前权和最高的情况下，尽量为每个boy找到权更大的边。

找的过程就是DFS过程，标记出S和T集是为了保证权和最大，因为只要帮S中任意一个boy另找一个女对象，为这个boy的此次脱单之路告终。

　　DFS的要完成的任务：

　　（1）标记S和T集。

　　（2）更新每个girl的slack值为最小。

　　模板还是必须的，带满了注释，改自kuangbin的模板。

 /* KM算法：复杂度O(nx*nx*ny)

 * 完全二分图求最大权匹配(必须为所有boy找到对象，且boy数量必须<=girl数量)

 * 若求最小权匹配，可将权值取相反数，结果取相反数

 * 点的编号从1开始。



 * 以男女模型出现比较直观。



 */

 int  nx, ny;                  //两边的点数，x为男，y为女。



 int  g[N][N];                 //二分图描述，g[x][y]表示边权。



 int  girl[N], Lx[N], Ly[N];   //girl[i]记录i的匹配成功对象，男女的顶标

 int  slack[N];      //为了优化用的，连接到对应girl的松弛值。



 bool S[N], T[N];    //匈牙利树的节点集合，S为男，T为女。



 bool DFS(int x) // x一定是boy

 {

     S[x]=true;

     for(int i=; i<=ny; i++) //枚举girl

     {

         if(T[i]) continue;

         int tmp=Lx[x]+Ly[i]-g[x][i];

         if( tmp== )

         {

             T[i]=true;

             //为第i个girl的男对象另找女对象

             if(girl[i]==- || DFS(girl[i]))

             {

                 girl[i]=x;      //记录匹配的boy

                 return true;

             }

         }

         else if(slack[i]>tmp)   //顺便更新下slack

             slack[i]=tmp;

     }

     return false;

 }

 int KM()

 {

     memset(girl, -, sizeof(girl));

     memset(Ly, , sizeof(Ly));

     for(int i=; i<=nx; i++) //初始化两个L数组分别为-INF和0

     {

         Lx[i] = -INF;

         for(int j=; j<=ny; j++)

             if(g[i][j]>Lx[i])    Lx[i]=g[i][j];

     }

     for(int j=; j<=nx; j++)     //枚举boy

     {

         for(int i=; i<=ny; i++) //初始slack为无穷。

slack只需要记录girl的。



             slack[i]=INF;

         while(true)     //无限循环，直到帮boy[j]找到对象

         {

             memset(S, , sizeof(S));

             memset(T, , sizeof(T));

             if( DFS(j) )  break;    //直接就找到对象了，搞定。



             int d=INF;

             for(int i=; i<=ny; i++)    //根据不在匈牙利树上的girl的slack值找到最小值d

                 if(!T[i] && d>slack[i])

                     d=slack[i];

             for(int i=; i<=nx; i++)     //所有匈牙利树上的boy更新lx值

                 if(S[i])    Lx[i]-=d;

             for(int i=; i<=ny; i++)     //树上的girl加d，不在树上的girl的slack减d。



             {

                 if(T[i])     Ly[i]+=d;   //这是为了让等式仍然成立

                 else         slack[i]-=d;

             }

         }

     }

     int ans=;

     for(int i=; i<=ny; i++) //累计匹配边的权和

         if(girl[i]>) ans+=g[girl[i]][i];

     return ans;

 }

KM算法