题意：
有n个Supervisor和Supervisee，他们之间相互有一个评分，现在要求一个匹配，所有人的评分和最小，并输出使评分和最小的所有匹配方案。
分析：
KM算法求二分图的最小权匹配，并用dfs输出所有方案。
代码：
//poj 2400
//sep9
#include <iostream>
using namespace std;
const int maxN=16;
char g[maxN][maxN];
int mx[maxN],my[maxN],hx[maxN],hy[maxN];
int w[maxN][maxN];
int lx[maxN],ly[maxN],linky[maxN];
int visx[maxN],visy[maxN];
int slack[maxN];
int nx,ny,pairNum;
int flag[maxN],match[maxN];
bool find(int x)
{visx[x]=true;for(int y=0;y<ny;++y){if(visy[y])continue;int t=lx[x]+ly[y]-w[x][y];if(t==0){visy[y]=true;if(linky[y]==-1||find(linky[y])){linky[y]=x;return true;}}else if(slack[y]>t)slack[y]=t;} return false;
}int KM()
{int i,j;memset(linky,-1,sizeof(linky));memset(ly,0,sizeof(ly));for(i=0;i<nx;++i)for(j=0,lx[i]=INT_MIN;j<ny;++j)if(w[i][j]>lx[i])lx[i]=w[i][j];for(int x=0;x<nx;++x){for(i=0;i<ny;++i)slack[i]=INT_MAX;while(1){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(find(x))break;int d=INT_MAX;for(i=0;i<ny;++i)if(!visy[i]&&slack[i]<d)d=slack[i]; if(d==INT_MAX)return -1;for(i=0;i<nx;++i)if(visx[i])lx[i]-=d;for(i=0;i<ny;++i)if(visy[i])ly[i]+=d;elseslack[i]-=d;}}int result=0;for(i=0;i<ny;++i)if(linky[i]>-1)result+=w[linky[i]][i];return result;
}void KM_dfs(int tot,int x)
{int i;if(tot<0)return ;if(tot==0&&x==nx){printf("Best Pairing %d\n",++pairNum);for(i=0;i<nx;++i)printf("Supervisor %d with Employee %d\n",i+1,match[i]+1); return ;} for(i=0;i<ny;++i)if(flag[i]==0){flag[i]=1;match[x]=i;KM_dfs(tot+w[x][i],x+1);flag[i]=0; }return ;
}int main()
{int cases,caseNum,sum;caseNum=0;scanf("%d",&cases);while(cases--){int n,i,j,x;memset(w,0,sizeof(w));scanf("%d",&n);for(i=1;i<=n;++i) for(j=0;j<n;++j){scanf("%d",&x);w[x-1][i-1]-=j;}for(i=1;i<=n;++i) for(j=0;j<n;++j){scanf("%d",&x);w[i-1][x-1]-=j;}nx=ny=n;int ans=-KM(); printf("Data Set %d, Best average difference: %.6lf\n",++caseNum,0.5*ans/n);pairNum=0;memset(flag,0,sizeof(flag));KM_dfs(ans,0);printf("\n");} return 0;
}