POJ2400 Supervisor, Supervisee 最小权匹配

　　话说光理解题意就搞了很久啊，说说题意吧：公司有n个管理者要招聘n个员工，所以每个管理者对每个员工进行面试，然后管理者和员工相互做出评价，每个管理者要对每个员工打分，同样每个员工要对每个管理者打分，分数越低评价越高，分数范围0,n-1。题目要求你对管理者和员工进行配对，要求所有配对的管理者和员工的分数之和最小，并且输出所有的情况。

　　这个题目的难点就是要求所有的情况，我一开始想的就是枚举全排列做了，但看到数据量n<15，枚举是O(n!)，如果数据恶心点，那么也会超时！想了一天，实在是没有其他的方法啊！其实n<15也已经暗示了要枚举做的啊！DFS试试，果然63ms就A了！看来以后还得把题目看得透一点！回想自己做区预赛的题目，每次也是遇到时间复杂度理论上限铁定会超时的时候，都不敢动手，但赛后发现，其实很多是可以搞的，所以经验还有待加强啊！ PS：这题数据是反的= =。

  1 //STATUS:G++_AC_63MS_716KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 using namespace std;
 13 #define LL long long
 14 #define Max(a,b) ((a)>(b)?(a):(b))
 15 #define Min(a,b) ((a)<(b)?(a):(b))
 16 #define mem(a,b) memset(a,b,sizeof(a))
 17 #define lson l,mid,rt<<1
 18 #define rson mid+1,r,rt<<1|1
 19 const int MAX=20,INF=200000000;
 20 
 21 int w[MAX][MAX],S[MAX],T[MAX],lx[MAX],ly[MAX],A[MAX],y[MAX],vis[MAX];
 22 int Tu,n,ans,anscou,slack;
 23 
 24 int match(int u)
 25 {
 26     int v,t;
 27     S[u]=1;
 28     for(v=1;v<=n;v++){
 29         t=w[u][v]-lx[u]-ly[v];
 30         if(!t){
 31             if(!T[v]){
 32                 T[v]=1;
 33                 if(!y[v] || match(y[v])){
 34                     y[v]=u;
 35                     return 1;
 36                 }
 37             }
 38         }
 39         else if(t<slack)slack=t;
 40     }
 41     return 0;
 42 }
 43 
 44 void KM()
 45 {
 46     int i,j,a;
 47     mem(ly,0);
 48     for(i=1;i<=n;i++){
 49         lx[i]=w[i][1];
 50         for(j=2;j<=n;j++)
 51             if(w[i][j]<lx[i])lx[i]=w[i][j];
 52     }
 53     for(i=1;i<=n;i++){
 54         while(1){
 55             slack=INF;
 56             mem(S,0);mem(T,0);
 57             if(match(i))break;
 58             for(j=1;j<=n;j++){
 59                 if(S[j])lx[j]+=slack;
 60                 if(T[j])ly[j]-=slack;
 61             }
 62         }
 63     }
 64 }
 65 
 66 void dfs(int cur,int s)
 67 {
 68     if(s>ans || (cur==n+1 && s!=ans))return ;
 69     int i;
 70     if(cur==n+1){
 71         printf("Best Pairing %d\n",anscou++);
 72         for(i=1;i<=n;i++)
 73             printf("Supervisor %d with Employee %d\n",i,A[i]);
 74         return ;
 75     }
 76     for(i=1;i<=n;i++){
 77         if(!vis[i]){
 78             vis[i]=1;
 79             A[cur]=i;
 80             dfs(cur+1,s+w[cur][i]);
 81             vis[i]=0;
 82         }
 83     }
 84 }
 85 
 86 int main()
 87 {
 88  //   freopen("in.txt","r",stdin);
 89     int i,j,t,k=1;
 90     scanf("%d",&Tu);
 91     while(Tu--)
 92     {
 93         mem(y,0);
 94         scanf("%d",&n);
 95         for(i=1;i<=n;i++){
 96             for(j=0;j<n;j++){
 97                 scanf("%d",&t);
 98                 w[t][i]=j;
 99             }
100         }
101         for(i=1;i<=n;i++){
102             for(j=0;j<n;j++){
103                 scanf("%d",&t);
104                 w[i][t]+=j;
105             }
106         }
107 
108         KM();
109 
110         for(ans=0,i=1;i<=n;i++)
111             ans+=w[y[i]][i];
112         printf("Data Set %d, Best average difference: %.6f\n",k++,ans*0.5/n);
113         anscou=1;
114         mem(vis,0);
115         dfs(1,0);
116         if(Tu)putchar('\n');
117     }
118     return 0;
119 }