POJ 2400 Supervisor, Supervisee（KM）

題意：N个部门和N个员工，每个部门要雇佣一个工人，部门对每个工人打分，从1~N，1表示很想要，N表示特别不想要，每个工人对部门打分，从1~N。1表示很想去这个部门，N表示特别不想去这个部门，求一个匹配，使每个人的希望值最大。

思路：KM算法。资料。用深搜构造所有能达到最大值的匹配情况。参考

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 
  5 using namespace std ;
  6 
  7 const int maxn = 110 ;
  8 int lx[maxn],ly[maxn] ;
  9 int left[maxn], n;
 10 bool S[maxn],T[maxn] ;
 11 int w[maxn][maxn] ;
 12 int slack[maxn] ;
 13 int y[maxn],cnt ;
 14 int ans;
 15 
 16 bool match(int x)
 17 {
 18     S[x] = true ;
 19     for(int j = 1 ; j <= n ; j++)
 20     {
 21         if(lx[x]+ly[j] == w[x][j] && !T[j])
 22         {
 23             T[j] = true ;
 24             if(!left[j] || match(left[j]))
 25             {
 26                 left[j] = x ;
 27                 return true ;
 28             }
 29         }
 30         else slack[j] = min(slack[j],w[x][j]-lx[x]-ly[j]) ;
 31     }
 32     return false ;
 33 }
 34 
 35 void KM()
 36 {
 37     for(int i = 1 ; i <= n ; i++)
 38     {
 39         left[i] = ly[i] = 0 ;
 40         lx[i] = 9999999;
 41         for(int j = 1 ; j <= n ; j++)
 42             lx[i] = min(lx[i],w[i][j]) ;
 43     }
 44     for(int x = 1 ; x <= n ; x++)
 45     {
 46         for(int i = 1 ; i <= n ; i++)
 47             slack[i] = 9999999 ;
 48         while(1)
 49         {
 50             memset(S,false,sizeof(S)) ;
 51             memset(T,false,sizeof(T)) ;
 52             if(match(x)) break ;
 53             int tmp = 9999999 ;
 54             for(int i = 1 ; i <= n ; i++)
 55                 if(!T[i])
 56                     tmp = min(tmp,slack[i]) ;
 57             if(tmp == 9999999)return ;
 58             for(int i = 1 ; i <= n ; i++)
 59             {
 60                 if(S[i]) lx[i] += tmp ;
 61                 if(T[i]) ly[i] -= tmp ;
 62             }
 63         }
 64     }
 65 }
 66 
 67 void dfs(int t,int sum)
 68 {
 69     if(sum > ans) return ;
 70     if(t > n)
 71     {
 72         if(sum != ans) return ;
 73         printf("Best Pairing %d
",++cnt) ;
 74         for(int j = 1 ; j <= n ; j++)
 75             printf("Supervisor %d with Employee %d
",j,y[j]) ;
 76         return  ;
 77     }
 78     for(int i = 1 ; i <= n ; i++)
 79     {
 80         if(!T[i])
 81         {
 82             y[t] = i ;
 83             T[i] = true ;
 84             dfs(t+1,sum+w[t][i]) ;
 85             T[i] = false ;
 86         }
 87     }
 88     return ;
 89 }
 90 int main()
 91 {
 92     int t,x ;
 93     scanf("%d", &t) ;
 94     for(int k = 1 ; k <= t  ; k++)
 95     {
 96         for(int i = 1 ; i <= n ; i++)
 97             for(int j = 1 ; j <= n ; j++)
 98                 w[i][j] = 0 ;
 99         scanf("%d",&n) ;
100         for(int i = 1 ; i <= n ; i++)
101             for(int j = 0 ; j < n ; j++)
102             {
103                 scanf("%d",&x) ;
104                 w[x][i] += j ;
105             }
106         for(int i = 1 ; i <= n ; i++)
107             for(int j = 0 ; j < n ; j++)
108             {
109                 scanf("%d",&x) ;
110                 w[i][x] += j ;
111             }
112         KM() ;
113         ans = 0 ;
114         cnt = 0 ;
115         for(int i = 1 ; i <= n  ; i++)
116             if(left[i])
117                 ans += w[left[i]][i] ;
118         printf("Data Set %d, Best average difference: %.6f
",k,ans/(2.0*n)) ;
119         memset(T,false,sizeof(T)) ;
120         dfs(1,0) ;
121         printf("
") ;
122     }
123     return 0 ;
124 }

View Code