题解：
最少平均分值是等于最佳匹配的权值和除上一个总的点数2*n
注意输入反过来
代码：
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> const int N=21; int n,lx[N],ly[N],T,w[N][N],k,d[N],t,ans,num,h[N],px[N],py[N]; int dfs1(int x) { px[x]=1; for (int i=1;i<=n;i++) { if (py[i])continue; t=lx[x]+ly[i]-w[x][i]; if (!t) { py[i]=1; if (!d[i]||dfs1(d[i])) { d[i]=x; return 1; } } } return 0; } void dfs2(int x,int sum) { if (sum>ans) return; if (x>n) { if (sum!=ans)return; printf("Best Pairing %d ",++num); for (int i=1;i<=n;i++) printf("Supervisor %d with Employee %d ",i,h[i]); return; } for (int i=1;i<=n;i++) if (!py[i]) { h[x]=i; py[i]=1; dfs2(x+1,sum-w[x][i]); py[i]=0; } return; } int main() { scanf("%d",&T); for (int u=1;u<=T;u++) { scanf("%d",&n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { scanf("%d",&k); w[k][i]=1-j; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { scanf("%d",&k); w[i][k]+=1-j; } memset(ly,0,sizeof(ly)); for (int i=1;i<=n;i++) { lx[i]=w[i][1]; for (int j=2;j<=n;j++) if (lx[i]<w[i][j])lx[i]=w[i][j]; } memset(d,0,sizeof(d)); for (int i=1;i<=n;i++) while (1) { memset(px,false,sizeof(px)); memset(py,false,sizeof(py)); if (dfs1(i)) break; t=1e9; for (int j=1;j<=n;j++) if (px[j]) for (int k=1;k<=n;k++) if (!py[k]&&lx[j]+ly[k]-w[j][k]<t) t=lx[j]+ly[k]-w[j][k]; for (int j=1;j<=n;j++) { if (px[j]) lx[j]-=t; if (py[j]) ly[j]+=t; } } ans=0; for (int i=1;i<=n;i++) if (d[i]!=0)ans-=w[d[i]][i]; printf("Data Set %d, Best average difference: %.6f ",u,ans*0.5/n); num=0; memset(h,0,sizeof(h)); memset(py,false,sizeof(py)); dfs2(1,0); if (u<T)puts(""); } return 0; }