当前位置:网站首页>The best match of p1559 athletes

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[25][25],q[25][25],n,c[25],ans;
bool vis[25];
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;
}

 

版权声明
本文为[Weihe]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/06/20210606234503686I.html