运动员最佳匹配问题

【问题描述】

羽毛球队有男女运动员各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]。设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

【输入形式】

第一行是男队员（或女队员）的个数，第二、三、四行是男运动员i 和女运动员j配对组成混合双打的男运动员竞赛优势，第五、六、七行是女运动员i和男运动员j配合的女运动员竞赛优势

【输出形式】

竞赛优势的最大和

【样例输入】

3

10 2 3

2 3 4

3 4 5

2 2 2

3 5 3

4 5 1

【样例输出】

52

【样例输入】

5

4 1 8 9 2

1 5 6 9 4

4 7 8 6 7

8 4 6 7 1

1 4 9 3 2

3 2 8 1 4

2 1 6 1 5

4 2 9 7 4

1 5 3 9 4

4 8 5 3 1

【样例输出】

199

#include<iostream>
#include<limits.h>
using namespace std;
const int N=10010;
int n;
int A[N][N],B[N][N];
bool st[N];//表示女运动员是否找到配合的人 
int tmp,ans=-INT_MAX,cnt;
void solve(int k)//k表示男运动员,同时是A矩阵的行
{
	for(int j=1;j<=n;j++)//j表示女运动员,也是A矩阵的列
	{
		if(!st[j])
		{
			tmp+=A[k][j]*B[j][k];
			st[j]=true;
			if(k!=n)
			{
				solve(k+1);
			}
			else
			{
				if(tmp>ans)
					ans=tmp;
			}
			tmp-=A[k][j]*B[j][k];
			st[j]=false;
		}
	}	
} 
int main()
{
	cin>>n;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>A[i][j];
			
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>B[i][j];
			
	solve(1);
	
	cout<<ans<<endl;
	
	return 0;
}