# The best match of p1559 athletes

2021-07-22 02:54:19 Weihe

## Title Description

There are male and female players in the badminton team n people . Given 2 individual n×n matrix P and Q.P[i][j] It's a male athlete i And female athletes j Competitive advantage of male athletes in mixed doubles ;Q[i][j] It's a female athlete i And male athletes j Match advantage of female athletes . Due to various factors such as technical cooperation and psychological state ,P[i][j] Not necessarily equal to Q[j][i]. Male athletes i And female athletes j The competitive advantages of men and women in the mixed doubles are P[i][j]*Q[j][i]. Design an algorithm , Calculating the best match of male and female athletes , To maximize the sum of competitive advantages of men and women in each group .

## I / O format

Input format ：

The first line has 1 A positive integer n (1≤n≤20). Next 2n That's ok , Each row n Number . front n Line is p, after n Line is q.

Output format ：

Output the maximum value of the sum of the competitive advantages of men and women .

## I/o sample

sample input #1：
```3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1```
sample output #1：
`52`

Solution：

The problem is actually KM Or the cost flow board , But given the small size of the data , So violent search pruning .

Direct search , Plus the possibility of pruning ：

Preprocessing \$n\$ The maximum value of each pair of combinations , If the current value is added with the accumulated maximum value that can be obtained later \$<ans\$, Then cut it off .

Code ：

```#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N=100005;
ll p,q,n,c,ans;
bool vis;
il void dfs(int x,ll tot)
{
if(x>n){ans=max(ans,tot);return;}
ll op=0;
for(int i=x;i<=n;i++)op+=c[i];
if(ans>op+tot)return;
for(int i=1;i<=n;i++)
if(!vis[i]){
vis[i]=1;
dfs(x+1,tot+p[x][i]*q[i][x]);
vis[i]=0;
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>p[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>q[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)c[i]=max(c[i],p[i][j]*q[j][i]);
dfs(1,0);
cout<<ans;
return 0;
}```

https://chowdera.com/2021/06/20210606234503686I.html