【POJ 2400】 Supervisor, Supervisee（KM求最小权匹配）

Supervisor, Supervisee

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2538		Accepted: 719

Description

Suppose some supervisors each get to hire a new person for their department. There are N people to be placed in these N departments. Each supervisor interviews all N people, and ranks them according to how much she wants each of them in her department (1 being "really want" and N being "really don't want"). In turn, each of the N candidates ranks each of the supervisors as to how much that person would like to work for that supervisor (again, 1 is "really want to work for him/her" and N is "really don't want to work for him/her"). Given the scores that each supervisor has for each candidate, and the scores each candidate has for each manager, write a computer program to determine the "best match" of candidates to supervisors. The "best match" is determined by finding the distribution that leads to the highest overall (i.e. sum of) satisfaction for all people. The closer a person is to her number one choice, the better. If everyone gets their number one choice, the average difference will be 0.

Input

The first line of the input will contain a single integer greater than 0 specifying the number of test cases.

The next line will contain a single integer value N, 0 < N < 15, representing the number of supervisors (and the number of employees - there are N supervisors and N employees). The next N lines will be the preferences of each of the N supervisors. Each line will contain N integer entries (1 through N for employees 1 through N), each separated by a space character, that represents the preferences of that supervisor from most preferred to least preferred. More specifically, the first entry on the line will represent that supervisor's first choice, the second entry her second, and so on. The next N lines will be the preferences of the N employees, in the same format as the supervisors.

All lines of data in the input file will end with an empty line.

Output

For each test case, write the test case number (starting with 1) followed by the best average difference written to six digits of precision to the right of the decimal point. On the next line, show which best match it was (starting with 1). On the next N lines, show each supervisor (starting with 1) followed by the employee with which she was matched (1 per line). NOTE: if there is more than one best match, matches should be listed in ascending permuted order (see sample output).

Separate each data set with an empty line.

Sample Input

2
7
1 2 3 4 5 6 7
2 1 3 4 5 6 7
3 1 2 4 5 6 7
4 1 2 3 5 6 7
5 1 2 3 4 6 7
6 1 2 3 4 5 7
7 1 2 3 4 5 6
1 2 3 4 5 6 7
2 1 3 4 5 6 7
3 1 2 4 5 6 7
4 1 2 3 5 6 7
5 1 2 3 4 6 7
6 1 2 3 4 5 7
7 1 2 3 4 5 6

2
1 2
2 1
1 2
1 2

Sample Output

Data Set 1, Best average difference: 0.000000
Best Pairing 1
Supervisor 1 with Employee 1
Supervisor 2 with Employee 2
Supervisor 3 with Employee 3
Supervisor 4 with Employee 4
Supervisor 5 with Employee 5
Supervisor 6 with Employee 6
Supervisor 7 with Employee 7

Data Set 2, Best average difference: 0.250000
Best Pairing 1
Supervisor 1 with Employee 1
Supervisor 2 with Employee 2

Source

Tehran 2003 Preliminary

题目大意就是n个上司与n名员工。每一个上司相应有想要搭配的员工。相同每一个员工有渴望搭配的上司。

输入第一行为N 之后n行为1~n号上司的期望从左到右从最好到最差

相同之后n行是1~n号员工

匹配到最渴望的人值为0，否则从左到右一次加1

要求问平均期望的最小值，也就是最小值/2n

最小值用KM最小权匹配计算就可以，因为还要求输出解，有多解则输出多解。所以还要搜一下……

事实上数据非常少。找最小权匹配也用搜的也能够。

。

代码例如以下：

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const double eps = 1e-8;

int mp[23][33];
int lx[33],ly[33],link[33],slack[33],next[33];
bool visx[33],visy[33],vis[33];
int n,ans,cnt;

bool cal(int x)
{
	visx[x] = 1;

	for(int y = 0; y < n; ++y)
	{
		if(visy[y]) continue;
		
		int t = lx[x]+ly[y]-mp[x][y];
		if(t == 0)
		{
			visy[y] = 1;
			if(link[y] == -1 || cal(link[y]))
			{
				link[y] = x;
				return 1;
			}
		}
		else slack[y] = min(slack[y],t);
	}
	return 0;
}

int KM()
{
	memset(link,-1,sizeof(link));

	for(int i = 0; i < n; ++i)
	{
		memset(slack,INF,sizeof(slack));
		while(1)
		{
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));

			if(cal(i)) break;

			int d = INF;
			for(int i = 0; i < n; ++i)
				if(!visy[i]) d = min(d,slack[i]);

			for(int i = 0; i < n; ++i)
				if(visx[i]) lx[i] -= d;

			for(int i = 0; i < n; ++i)
				if(visy[i]) ly[i] += d;
				else slack[i] -= d;
		}
	}

	ans = 0;
	for(int i = 0; i < n; ++i)
		if(link[i] != -1) ans += mp[link[i]][i];

	return -ans;
}

void dfs(int id,int hs)
{
	if(hs < ans) return;
	if(id == n)
	{
		if(hs == ans)
		{
			printf("Best Pairing %d
",++cnt);
			for(int i = 0; i < n; ++i)
			{
				printf("Supervisor %d with Employee %d
",i+1,next[i]+1);
			}
		}
		return;
	}

	for(int i = 0; i < n; ++i)
	{
		if(vis[i]) continue;
		vis[i] = 1;
		next[id] = i;
		dfs(id+1,hs+mp[id][i]);
		vis[i] = 0;
	}
}

int main()
{
	int t,x;
	scanf("%d",&t);
	
	for(int z = 1; z <= t; ++z)
	{
		scanf("%d",&n);
		memset(ly,0,sizeof(ly));

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

		for(int i = 0; i < n; ++i)
			for(int j = 0; j < n; ++j)
			{
				scanf("%d",&x);
				mp[i][x-1] -= j;
				if(j == 0) lx[i] = mp[i][x-1];
				else lx[i] = max(lx[i],mp[i][x-1]);
			}

		printf("Data Set %d, Best average difference: %.6f
",z,KM()*0.5/n);

		cnt = 0;
		memset(vis,0,sizeof(vis));
		dfs(0,0);
		puts("");
	}

	return 0;
}