厦门理工学院oj 1106 -- 最佳拍档

一道简单的dfs+回溯，首先要考虑到一个新的数组c（从学长那里偷的kkkk），c[i][j]表示i号男生与j号女生组成的竞赛优势，dfs中的参数u记录着当前遍历到的第几行，st数组用来存储选取了哪些列，这道题退化成了一道弱化的八皇后问题，即不允许任何一行/一列出现一个以上的元素被选取（即出现一名男生/女生与多名女生/男生配对的情况），当遍历到第n+1行时退出，更新最大值

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 12, M = 110;

int a[N][N], b[N][N], c[N][N];
bool st[N];
int n, m;
int ans;

void dfs(int u, int res)
{
    if(u == n + 1) 
    {
        ans = max(ans, res);
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            st[i] = true;
            dfs(u + 1, res + c[u][i]);
            st[i] = false;
        }
    } 
    return;
}

int main()
{
    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];
        }
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}