#P1559. 运动员最佳匹配问题

运动员最佳匹配问题

题目描述

羽毛球队有男女运动员各 nn 人。给定 22n×nn \times n 矩阵 PPQQPi,jP_{i,j} 是男运动员 ii 和女运动员 jj 配对组成混合双打的男运动员竞赛优势;Qi,jQ_{i,j} 是女运动员 ii 和男运动员 jj 配合的女运动员竞赛优势。

但是,由于技术配合和心理状态等各种因素影响,Pi,jP_{i,j} 不一定等于 Qj,iQ_{j,i}。男运动员 ii 和女运动员 jj 配对组成混合双打的男女双方竞赛优势为 Pi,j×Qj,i\bm{P_{i,j} \times Q_{j,i}}

现在,请你设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。

输入格式

第一行有 11 个正整数 nn (1n20)(1 \le n \le 20)。接下来的 2n2n 行,每行 nn 个数。前 nn 行是 PP,后 nn 行是 QQ

输出格式

将计算出的男女双方竞赛优势的总和的最大值输出。

3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
52