学步园

                            想看更多的解题报告:http://blog.csdn.net/wangjian8006/article/details/7870410
                              转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意：
有n个老板和n个员工，他们对彼此有一个排名，现在要求选出最好的对应关系使他们平均分值最少

有n个老板和n个员工,首先给出有多少组测试数据，然后给出n
接下来n行，每行有n个数，第i行代表第i个老板对所有员工的喜好排名，排在第一个员工的标号的权值为0，第二个为-1，依次递减
再有n行，每行n个数，代表员工对老板的排名，排在第一个老板的标号的权值为0，第二个为-1，依次递减
这里权值为给对方所评的分数

这里要注意的是，题目的那个矩阵给反了，有可能是题目描述有问题，看discuss才知道的，否则会一直WA
将那个矩阵反过来输入试试就A了,我是将行看成老板，列看成员工的

找出最少平均分值之后，还要输出哪个老板和哪个员工匹配。如果有多个匹配，按字典序输出

解题思路：最少平均分值，用KM找出最佳匹配，使得权值和最小即可，当然他们的权值全为负数，所以当输出的时候要算出相反数

最少平均分值是等于最佳匹配的权值和除上一个总的点数2*n
找出了最少平均分值，最后那个匹配输出直接全排列找匹配，如果他们的权值和等于最佳匹配的权值和，就输出这种情况，直到全排列完即可。

/*
Memory 196K
Time   79MS
*/
#include <iostream>
using namespace std;
#define INF INT_MAX
#define MAXV 16
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)

int n,sum,cost;
int ly[MAXV],lx[MAXV],link[MAXV],tx[MAXV],ty[MAXV];
int map[MAXV][MAXV],mark[MAXV];

void init(){					//KM初始化
	int i,j;
	memset(link,-1,sizeof(link));
	cost=0;

	for(i=1;i<=n;i++) {ly[i]=0;lx[i]=map[i][1];}

	for(i=1;i<=n;i++){
		for(j=2;j<=n;j++)
			lx[i]=max(lx[i],map[i][j]);
	}
}

int hungary(int x){				//匈牙利找出完美匹配
	int i;
	tx[x]=1;
	for(i=1;i<=n;i++){
		if(!ty[i] && map[x][i]==lx[x]+ly[i]){
			ty[i]=1;
			if(link[i]==-1 || hungary(link[i])) {
				link[i]=x;
				return 1;
			}
		}
	}
	return false;
}

int km(){
	int i,tmp,j,k;
	init();

	for(i=1;i<=n;i++){
		while(1){
			memset(tx,0,sizeof(tx));
			memset(ty,0,sizeof(ty));

			if(hungary(i)) break;

			tmp=INF;
			for(j=1;j<=n;j++){
				if(tx[j]){
					for(k=1;k<=n;k++){
						if(!ty[k]){
							tmp=min(tmp,lx[j]+ly[k]-map[j][k]);
						}
					}
				}
			}

			for(j=1;j<=n;j++) {
                if(tx[j]) lx[j]-=tmp;
                if(ty[j]) ly[j]+=tmp;
            }
		}
	}
	for(i=1;i<=n;i++)
		if(link[i]!=-1) cost+=map[link[i]][i];

    return -cost;			//因为求出的最佳匹配的权值是负的，所以输出相反值
}

void dfs(int cap,int x){		//全排列搜索找出所有答案
	if(x<cost) return ;
	if(cap>n){
		if(x!=cost) return ;
		printf("Best Pairing %d\n",++sum);
		for(int i=1;i<=n;i++)
			printf("Supervisor %d with Employee %d\n",i,link[i]);
	}else{
		for(int i=1;i<=n;i++){
			if(!mark[i]){
				mark[i]=1;
				link[cap]=i;
				dfs(cap+1,x+map[cap][i]);
				mark[i]=0;
			}
		}
	}
}

int main(){
	int t,i,j,cnt,x;
	scanf("%d",&t);
	for(cnt=1;cnt<=t;cnt++){
		memset(map,0,sizeof(map));

		scanf("%d",&n);
		for(i=1;i<=n;i++){
			for(j=0;j<n;j++){
				scanf("%d",&x);
				map[x][i]-=j;
			}
		}

		for(i=1;i<=n;i++){
			for(j=0;j<n;j++){
				scanf("%d",&x);
				map[i][x]-=j;
			}
		}
		//平均差异是最佳匹配权值km()和除上总的点数2*n
		printf("Data Set %d, Best average difference: %.6lf\n",cnt,0.5*km()/n);

		sum=0;
		memset(mark,0,sizeof(mark));
		dfs(1,0);
		printf("\n");
	}
	return 0;
}