运动员最佳匹配问题
Description
羽毛球队有男女运动员各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
将计算出的男女双方竞赛优势的总和的最大值输出。
Samples
Sample #1
Input
3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
Output
52
分析：
深度搜索+剪枝算法
固定男运动员，对女运动员进行一次全排列，并求出每位男运动员能匹配到的最大优势值。本题共有n！种配对情况。
固定1号男运动员，让所有的n个女运动员与其匹配，经过n次匹配，分别保存每组男女运动员的匹配优势到res数组和最优的男女运动员优势到maxsum数组。
其中，d数组是N×N的二维数组，用于保存每个男运动员匹配过的女运动员的优势；maxsum是一个1×N的一维数组，用于保存每个男运动员的匹配的最佳女运动员的优势。
若贪心的加上其余运动员匹配最大优势后，仍不能超过已经搜索出的最优解，那么向下搜完整颗子树也不会得到最优解，则要进行剪枝操作。因为再向下搜索的结果只可能是小于等于最大优势的。
具体为这段代码：
int cnt=0;
for(int i=t;i<n;i++)//记录该男生及此后的男生所有的最大竞争优势之和
cnt+=maxsum[i];
//将和与之前的竞争优势相加，并与当前最大的总竞争优势比较
//若小于，则说明之后不可能存在比当前最大竞争优势更大的数，
if(sum+cnt<m)//则直接返回 ，节省时间
return;
#include<iostream>
#include<vector>
using namespace std;
int a[21][21],b[21][21];
int d[21][21];
int maxsum[21]={
0};
int book[21]={
0};
int n,m=0,sum=0;
void dfs(int t){
//t对应遍历的行，即男生
if(t==n){
//遍历完毕
m=max(m,sum);//得每个方案对应最大的竞争优势
return;
}
int cnt=0;
for(int i=t;i<n;i++)//记录该男生及此后的男生所有的最大竞争优势之和
cnt+=maxsum[i];
//将和与之前的竞争优势相加，并与当前最大的总竞争优势比较
//若小于，则说明之后不可能存在比当前最大竞争优势更大的数，
if(sum+cnt<m)//则直接返回 ，节省时间
return;
for(int i=0;i<n;i++){
//遍历女生
if(!book[i]){
//如果该女生还未配对
book[i]=1;//将该女生和这个男生配对
sum+=d[t][i];//加上对应的竞争优势
dfs(t+1);//遍历下一个男生
book[i]=0;//返回后，将该女生取消配对
sum-=d[t][i];//减去对应的竞争优势
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>b[i][j];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
d[i][j]=a[i][j]*b[j][i];//记录每个男生和每个女生双打的竞争优势
maxsum[i]=max(maxsum[i],d[i][j]);//记录每个男生对应的最大的竞争优势
}
}
dfs(0);
cout<<m<<endl;
return 0;
}
