P1559 运动员最佳匹配问题 题解
本篇使用 \(\text{KM}\) 算法求解。
对于 \(\text{KM}\) 算法
步骤如下：
首先要用邻接矩阵存二分图，然后用贪心算法初始化标杆，运用匈牙利算法找到完美匹配，如果找不到则修改标杆增加一些边。重复以上步骤直到找到完美匹配。
标杆分为 \(X\) 标杆和 \(Y\) 标杆，一般把比较少的点放在 \(X\) 标杆一侧。
首先要初始化两个标杆分别为 \(X\) 标杆和 \(Y\) 标杆，\(X\) 标杆初始化为与之相连的最大边权，\(Y\) 标杆初始化为 \(0\)，且直接加入拥有最大边权的边。如果发现此时的匹配就是完美匹配，那么就直接退出，否则进行标杆的更改。从第一个节点开始扫描，如果有合法的增广路，那么将其反选，扩充路径，如果该节点没有合法的增广路，那么则将增广路上的所有的 \(X\) 标杆上的点加入点集 \(S\),将 \(Y\) 标杆上的所有点加入点集 \(T\)，从 \(S\) 和不在 \(T\) 集合中的点里面，计算 \(d=\min \left \{ L(x)+L(y)-w(x,y) \right \}\) 计算后，将在 \(S\) 点集内 \(x\) 的顶标减 \(d\)，在 \(T\) 的顶标加 \(d\)。并将目前没有加入二分图的权值和等于顶标和的边作为未匹配边加入到二分图中，然后再在该节点寻找增广路，如果还是没有，则再次通过更改标杆来增加边，直到有增广路出现为止。之后重复寻找增广路的步骤以及更改标杆的步骤，如果出现了完美匹配就直接退出。
本人的一点人话解释：
\(\text{KM}\) 算法一般用于解决寻找最优匹配的问题，是基于匈牙利算法的一种算法，和匈牙利相比，他多了个左右期望值。
左期望值的初值为它所连接的边的最大边权，右期望值的初值为 0 。如果左右期望值加起来的值等于边权的话，即匹配成功，否则不匹配，匹配失败的话我们需要 dfs 找出最小的能使其匹配成功的期望值，并将参与 dfs 的左期望值减去搜到的值，右期望值加上搜到的值并继续匹配。（没看明白的话请看下面大佬的博客理解吧，\(lz\) 水平实在有限 \(QAQ\) ）。
\(\text{KM}\) 算法详解，请点这里，同时内附匈牙利算法链接。
本题思路
我们可以将 \(i\) 号男运动员与 \(j\) 号女运动员匹配所得到的竞赛优势 \(P[i][j]\times Q[j][i]\) （如果你不知道为什么是 \(Q[j][i]\) 的话请仔细看题），只需要将他们的优势用邻接矩阵存起来在跑 \(\text{KM}\) 即可。（代码附详细注释）
\(Code\)
#include
#include
#include
#include
#include
#include
#define gc getchar
#include
#define reg register
#define ll long long
//#define int long long
using namespace std;
const int M=25;
const int N=1e5+5;
const int mod=998244353;
//const int INF = 0x3f3f3f3f;为了防止ctrl将这里注释掉了
inline void print(int x) {if (x < 0) putchar('-'), x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0');}
inline int read() { int res = 0, f = 0; char ch = gc();for (; !isdigit(ch); ch = gc()) f |= (ch == '-'); for (; isdigit(ch); ch = gc()) res = (res << 1) + (res << 3) + (ch ^ '0'); return f ? -res : res;}
int n,w,ans,mini;
int p[M],vis1[M],vis2[M],L[M],R[M],a[M][M];
//p数组记录匹配对象，vis1vis2分别标记左右部分的点，LR是左右期望值，a是处理边权的
inline int dfs(int u)//dfs匹配左右点
{
vis1[u]=1;//标记左半部分的点已经连接
for(reg int i=1;i<=n;i++)//遍历
{
if(!vis2[i])//如果右半部分的点没有被访问过
{
int x=L[u]+R[i]-a[u][i];//计算期望值和好感度的差
if(x==0)//如果结果为0，即期望值等于好感度
{
vis2[i]=1;//标记右节点
if(!p[i] || dfs(p[i]))//如果当前点没有与之匹配的点或者当前点所匹配的点还可与其他节点相匹配
{
p[i]=u;//匹配成功
return 1;//返回成功
}
}
else if(x>0)//如果期望值不等于好感值，则记录最小的差
mini=min(mini,x);
}
}
return 0;//匹配失败
}
inline void KM()
{
for(reg int i=1;i<=n;i++)
{
while(1)
{
mini=INF;//重置最小值
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));//重置vis数组
if(dfs(i)) break;//匹配成功了就退出
for(reg int j=1;j<=n;j++) if(vis1[j]) L[j]-=mini;//左期望值减去最小值
for(reg int j=1;j<=n;j++) if(vis2[j]) R[j]+=mini;//右期望值加上最小值
}
}
}
signed main()
{
n=read();
for(reg int i=1;i<=n;i++)
for (reg int j=1;j<=n;j++)
a[i][j]=read();//输入
for(reg int i=1;i<=n;i++)
for(reg int j=1;j<=n;j++)
w=read(),a[j][i]*=w; //求出边权
for(reg int i=1;i<=n;i++)
for(reg int j=1;j<=n;j++)
L[i]=max(a[i][j],L[i]);//求出左期望值
KM();//跑一遍KM算法
for(reg int i=1;i<=n;i++)
ans+=a[p[i]][i];//累加答案
printf("%d",ans);
return 0;
}