会python真的可以为所欲为0(回)
352天前
这里还有人吗1(回)
537天前这里还有人吗0(回)
537天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
762天前到处都是羊，不想上班0(回)
842天前
鸽子
0(回)
846天前
问题描述：
羽毛球队有男女运动员各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; |
} |
