B - 运动员最佳匹配问题 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 将计算出的男女双方竞赛优势的总和的最大值输出。 Sample Input
代码语言：javascript复制3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1Output
代码语言：javascript复制52#include<bits/stdc .h>
using namespace std;
int mark,n;
int a[22][22];
bool vis[22];
int pre[22];//增加剪枝条件
void dfs(int p,int co)
{
//jieshu
if(p > n &&co > mark)
{
mark = max(co,mark);//mark ：越来越高的要求
return;
}
//jianzhi
if(co pre[n] - pre[p-1] > mark)//判断当前未选择的前提下，后面的优势
{
for(int i = 1; i <= n; i )
{
if(vis[i] == false)
{
vis[i] =true;
dfs(p 1,co a[p][i]);
vis[i] =false;
}
}
}
}
int main()
{
mark =0;
scanf("%d",&n);
for(int i=1; i<=n; i )//1开始，防止越界 后面会出现 pre[p-1]
{
for(int j=1; j<=n; j )
{
scanf("%d",&a[i][j]);
}
vis[i] =false;
}
for(int i=1; i<=n; i )
{
for(int j=1; j<=n; j )
{
int x;
scanf("%d",&x);
a[j][i] *=x;
}
}
for(int i=1; i<=n; i )
{
for(int j=1; j<=n; j )
{
pre[i] =max(a[i][j],pre[i]);//第i个理想的男方最大优势
}
pre[i] =pre[i-1];//前i个理想的男方最大优势
}
dfs(1,0);
printf("%dn",mark);
}cin、cout也可以
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int a[22][22];
int b[22][22];
int c[22][22];
int pre[22];//前..个男方优势
int vis[22];//标记女方
int tot;
void dfs(int p,int q,int sum)
{
if(p > q && sum >tot)
{
tot=sum;
return;
}
if(sum pre[q]-pre[p-1] >tot)
{
for(int j =1; j<=q; j )
{
if(vis[j] == 0)
{
vis[j] =1;
dfs(p 1,q,sum c[p][j]);//go 去确定下一个
vis[j] =0;
}
}
}
}
int main()
{
int n;
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];
}
for(int i=1; i<=n; i )
{
for(int j=1; j<=n; j )
{
c[i][j] = a[i][j]*b[j][i];
pre[i]=max(pre[i],c[i][j]);
}
pre[i] =pre[i-1];//前i个理想的男方最大优势
}
tot =0;
dfs(1,n,0);//每个男方去确定一个女方，对女方标记
cout<<tot<<endl;
}
