题解 P1559 【运动员最佳匹配问题】+排列树解法+剪枝优化

好雨天堂 · 2018-04-21 09:23:45 · 题解

男运动员位置不动, 女运动员全排列, 回溯搜索最优值 解空间是n的全排列, 所以选择排列树作为解空间结构. 变量设计: 当前得分cw, 最佳得分maxValue, x[1:n]女运动员的排列 定义函数 f(i,m) = maxj=m+1n P[i][x[j]]*Q[x[j]][i], 其中i>m, 是在前m位男运动员已配对的情况下, 男运动员i配对其她女运动员的上界 定义函数 Upb(m) = f(m+1,m)+f(m+2,m)+…+f(n,m). 当前m位男运动员已配对的情况下, cw+Upb(m)是余下情况配对的上界, 由此可以设计剪枝(限制)条件 cw+Upb(m) > maxValue

#include<cstdio>  
#include<cstring>  
#include<climits>  
#include<algorithm>  
#include<stdio.h>
#include<iostream>
#define INF 0x7ffffff
using namespace std;
#define maxn 22
int n;
int p[maxn][maxn];
int q[maxn][maxn];
int x[maxn];
int cw;
int maxValue = 0;

/*
定义函数 f(i,m) = maxj=m+1n P[i][x[j]]*Q[x[j]][i], 其中i>m,
是在前m位男运动员已配对的情况下, 男运动员i配对其她女运动员的上界

*/
int f(int i, int m)
{
    int ans = 0;
    for (int j = m+1; j <= n; j++)
        ans = max(ans,p[i][x[j]]*q[x[j]][i]);
    return ans;
}
/*
定义函数 Upb(m) = f(m+1,m)+f(m+2,m)+…+f(n,m).
当前m位男运动员已配对的情况下, cs+Upb(m)是余下情况配对的上界,
由此可以设计剪枝(限制)条件 cs+Upb(m) > maxValue

*/
int Upb(int m)
{
    int sum = 0;
    for (int i = m+1 ; i <= n; i++)
        sum += f(i, m);
    return sum;
}
void backTrack(int t) {
    if (t > n) 
    {
        maxValue = max(maxValue, cw);
        return;
    }

        for (int i = t; i <= n; i++) 
        { 
            swap(x[i], x[t]); 
            cw += p[t][x[t]]*q[x[t]][t];
            if (cw + Upb(t) > maxValue)
            {
                backTrack(t + 1);
            }
            cw -= p[t][x[t]] * q[x[t]][t]; //回溯 
            swap(x[t], x[i]);
        }

}
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]);  
            }
        }
        for (int i = 1; i <= n; i++)
            x[i] = i;
        backTrack(1);
        printf("%d\n", maxValue); 
        return 0;
}