题解P1559

_Harrisonwhl_ · 2021-05-12 19:22:09 · 题解

因为范围偏小(n ≤ 20)，所以可以直接选择使用 dfs + 可行性剪枝

基本方法：搜索每个男运动员，为他去搜索匹配每一个未用过的女运动员，最后算出每种匹配的竞赛优势，并在所有方案里选最大。

如果直接暴力搜索，可获得 80 分，代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p[25][25],q[25][25],s,ans;
bool v[25]; //需要确定每个女运动员是否已匹配。
void dfs(int x)
{
    if (x > n)
    {
        ans = max(s,ans);
        return;
    }
    for (int i = 1;i <= n;i++)
        if (!v[i])
        {
            v[i] = 1;
            s += p[x][i] * q[i][x];
            dfs(x + 1);
            s -= p[x][i] * q[i][x];//不同方案需回溯。
            v[i] = 0;
        }
}
int main(){
    cin >> n;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            scanf("%d",&p[i][j]);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            scanf("%d",&q[i][j]);
    dfs(1);
    cout << ans;
    return 0;
}

我们可以通过剪枝来 AC 后面两个点，可以剪掉已经不可能的情况：就是在任何一种搜索中的情况下的竞赛优势理论最大值(不一定可以配出此情况，但是理论最大值肯定比实际最大值要大，所以如果理论最大值都没有已搜过的完整路的答案大，实际上按这条路搜下去必定无法更新答案，就是无意义的路径)+原来已搜部分仍然没有之前搜出的答案大，说明这条路已经不可能了，直接 return 返回。