B - 运动员最佳匹配问题------基于dfs的回溯思想

来杯Sherry

发布于 2023-05-25 13:59:12

2570

发布于 2023-05-25 13:59:12

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

Output

#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("%d\n",mark);
}

cin、cout也可以

#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;


}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-05-25，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs