运动员最佳配对问题 pascal 的

来源：百度知道 编辑：UC知道 时间：2024/06/07 12:53:24
运动员最佳配对问题。一个羽毛球队有男女运动员各n人，给定2个n*n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打时的竞赛优势；Q[i][j]则是女运动员i和男运动员j配合时的竞赛优势。显然，由于技术的配合和心理状态等各种因素的影响，P[i][j]不一定等于Q[j][i]。设计一个算法，计算出男女运动员的最佳配对法，使各组男女双方竞赛优势乘积的总和达到最大

急

dp的方法我没有想出来

我们可以得出任意一对合作的竞赛优势。我们构图，左边加一个源点，向每个女选手连一条边，容量为1费用为0；女选手向男选手连一条边，容量为1费用为他们合作的竞赛优势；右边加一个汇点，男选手向汇点连一条边，容量为1费用为0。在此图上做最大费用最大流

给个样例嘞，有样例好分析

DP?

对p[i][j]和q[i][j]取对数,在此基础上做二分图最大权匹配

具体方法可以用KM,也可以用费用流