KM最大匹配 HDU 2255

KM算法详解+模板 - wenr - 博客园  http://www.cnblogs.com/wenruo/p/5264235.html

 #include<iostream>
 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 using namespace std;

 #define MAXN 305
 #define inf 65553566
 int love[MAXN][MAXN];   /// 记录每个妹子和每个男生的好感度
 int ex_girl[MAXN];      /// 每个妹子的期望值
 int ex_boy[MAXN];       /// 每个男生的期望值
 bool vis_girl[MAXN];    /// 记录每一轮匹配匹配过的女生
 bool vis_boy[MAXN];     /// 记录每一轮匹配匹配过的男生
 int match[MAXN];        /// 记录每个男生匹配到的妹子 如果没有则为-1
 int slack[MAXN];        /// 记录每个汉子如果能被妹子倾心最少还需要多少期望值

 int n,sum;

 ///为女孩找匹配的男孩
 int find(int girl)
 {
     vis_girl[girl]=;
     for(int boy=;boy<=n;boy++)
     {
         if(vis_boy[boy]) continue;///如果男孩已经被标记过，则找下一个
         int gap=ex_girl[girl]+ex_boy[boy]-love[girl][boy];///看差距
         if(gap==)
         {
             vis_boy[boy]=;
             if(match[boy]==-||find(match[boy]))///如果男孩未匹配过或者该男孩的妹子可以找其他人
             {
                 match[boy]=girl;///将女孩匹配给男
                 return ;
             }
         }
         else
         {
             slack[boy]=min(slack[boy],gap);
         }
     }
     return ;
 }
 void KM()
 {
     memset(match,-,sizeof(match));
     memset(ex_boy,,sizeof(ex_boy));

     ///每个女生的初始期望值是与他相连的男生最大的好感度
     for(int i=;i<=n;i++)
     {
         ex_girl[i]=love[i][];
         for(int j=;j<=n;j++)
         {
             ex_girl[i]=max(ex_girl[i],love[i][j]);
         }
     }
     ///尝试为每个女孩匹配男孩
     for(int i=;i<=n;i++)
     {
         fill(slack+,slack+n+,inf);
         while()
         {

               /// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
               ///记录每轮匹配*女孩是否被尝试匹配过
             memset(vis_girl,,sizeof(vis_girl));
             memset(vis_boy,,sizeof(vis_boy));
             if(find(i))  break;///如果发现该女孩已经找到归宿，就进行下一个女孩
             int d=inf;
             for(int j=;j<=n;j++)
                 if(!vis_boy[j])///看该男孩如果没有匹配的，就将最小的期望值给他
                 d=min(d,slack[j]);

             for(int j=;j<=n;j++)
             {
                 if(vis_girl[j])///如果女孩已经匹配，则女孩的期望值减去
                     ex_girl[j]-=d;
                 if(vis_boy[j])
                     ex_boy[j]+=d;
             }
         }
     }
 }
 int main()
 {
     while(scanf("%d",&n)!=EOF)
     {
         sum=;
         for(int i=;i<=n;i++)
             for(int j=;j<=n;j++)
         {
             scanf("%d",&love[i][j]);
         }
         KM();
         for(int i=;i<=n;i++)
         {
             sum+=love[match[i]][i];
         }
         printf("%d\n",sum);
     }

 }