运动员最佳匹配问题

问题描述：

羽毛球队有男女运动员各n人。给定2个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

Input
每组测试数据第一行有1个正整数n(1≤n≤20)。接下来的2n行，每行n个数。前n行是p矩阵，后n行是q矩阵。

Output
输出男女双方竞赛优势总和的最大值。

Sample Input
3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1

Sample Output
52

#include<iostream>
using namespace std;
int a[22];
int p[22][22];
int q[22][22];
int n;
int sum=0;
void swap ( int &x,int &y )
{
	int temp=x;
	x=y;
	y=temp;
}
void Backtrack ( int t )
{
	if ( t>n )
	{
		int s=0;
		for ( int j=0; j<n; j++ )
		{
			s+=p[j][a[j+1]-1]*q[a[j+1]-1][j];
		}
		if ( s>=sum ) sum=s;
	}
	else
	{
		for ( int i=t; i<=n; i++ )
		{
			swap ( a[i],a[t] );
			Backtrack ( t+1 );
			swap ( a[i],a[t] );
		}
	}
}
int main()
{
	int i,j;
	while ( cin>>n )
	{
		for ( i=0; i<=n; i++ ) a[i]=i;
		for ( i=0; i<n; i++ )
		{
			for ( j=0; j<n; j++ )
			{
				cin>>p[i][j];
			}
		}
		for ( i=0; i<n; i++ )
		{
			for ( j=0; j<n; j++ )
			{
				cin>>q[i][j];
			}
		}
		Backtrack ( 1 );
		cout<<sum<<endl;
	}
	return 0;
}