P1559 运动员最佳匹配问题
住在隔壁小莘
·
2022-09-20 16:54:35
·
题解
通过读到 计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大 这么一句话，你应该很快就能想到这是有关于二分图最大权完美匹配的问题。
那么二分图最大权完美匹配相较于二分图完美匹配来说，是边权有了权值，不是单纯的为了让配对数更多（或者是搜索出配对数最多的配对方法等）。
其他题解对于 KM 算法已经讲解的非常透彻了，我这里就稍微说说连边。
看到这个题目，你会发现两个人之间都有关系，即 A 对 B 有一个值， B 对 A 也有一个值，而在以往做的时候可能只会出现 A 对 B 有一个值，因为 A 对 B 与 B 对 A 的值都是给定的，那么我们 合并这两个值，也就是题目中的 p[i][j] \times q[j][i]，那么 A 与 B 的连边的权值也就确定了，那么就可以跑 KM 算法啦。
/*
1. 设置最大期望值
2. 利用匈牙利算法找增广路
3. 找到增广路，匹配成功，退出
4. 找不到，最小程度降低男生期望，提升女生期望
5. 继续回到(2)开始重复
val1[N]/val2[N]分别记录U集与V集点的点权（匹配期望值）
vis1[N]/vis2[N]分别记录每次寻找增广路过程中U集与V集点的访问情况
match[N]记录最终U集内点匹配到的在V集内点的编号
slack[N]记录匹配过程中，U集内任意点能够选择V集内任意点作为匹配对象所需要降低val（期望值）的最小值
*/
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int INF=0x3f3f3f3f3f;
const int N=550;
int n,m,match[N],pri[N];
bool vis2[N];
long long a[N][N];
long long fav[N][N],val1[N],val2[N],sla[N];
void bfs(int k){
int x,y=0,z=0;
memset(pri,0,sizeof(pri));
memset(sla,INF,sizeof(sla));
match[0]=k;
do{
int d=INF;
x=match[y];
vis2[y]=true;
for(int i=1;i<=n;i++){
if(vis2[i]){
continue;
}
if(sla[i]>val1[x]+val2[i]-fav[x][i]){
sla[i]=val1[x]+val2[i]-fav[x][i];
pri[i]=y;
}
if(sla[i] d=sla[i]; z=i; } } for(int i=0;i<=n;i++){ if(vis2[i]){ val1[match[i]]-=d;val2[i]+=d; }else{ sla[i]-=d; } } y=z; }while(match[y]); while(y){ match[y]=match[pri[y]]; y=pri[y]; } } int KM(){ memset(match,0,sizeof(match)); memset(val1,0,sizeof(val1)); memset(val2,0,sizeof(val2)); for(int i=1;i<=n;i++){ memset(vis2,false,sizeof(vis2)); bfs(i); } int res=0; for(int i=1;i<=n;i++){ res+=fav[match[i]][i]; } return res; } signed 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++){ int k; cin>>k; a[j][i]*=k;//记得这里的j与i是反的，因为枚举是正着枚举的 } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ fav[i][j]=max(fav[i][j],a[i][j]); } } cout< }