题解 P1559 【运动员最佳匹配问题】

glorious_dream

·

2022-04-21 16:48:41

·

题解

题目大意：

给定每一对男女之间的优势，求如何组合能让优势的总和最大。

算法描述：

首先可以看出来，这道题是一个带权的二分图匹配，KM 算法的裸题。

这个博客写的很好

先来用自己的话简单的说一下。

读入数据之后，需要把我们记录的数组先求好，也就是 w[i][j] 表示 i 女与 j 男之间的优势，这个先处理好就可以。

然后说算法的核心。首先，需要先知道二分图最大匹配。

可以理解为中介帮你介绍房子的问题。给定两个集合，它们之间有一些边相连，但两个集合内部没有边相连，求最多能两个集合之间连多少条边。

著名的匈牙利算法！ 每次看能不能满足条件，更新匹配数。

二分图最大匹配模板题

bool find(int x){

for(re i(head[x]) ; i ; i=e[i].nxt){

int v=e[i].to;

if(!vis[v]){

vis[v] = 1;

if(!match[v]||find(match[v])){

match[v]=x;

return 1;

}

}

}

return 0;

}

然后来说这道题，上面那位大佬的博客讲的我觉得很清楚，当然也很生动形象。

需要在匈牙利算法的基础上，更新每一个左面和右面的点的"期望"。

先从第一个女生能找到的最大的边开始，依次往下找，如果遇到某一个女生找不到自己的最大值，那么往回找，看看已经找过的女生能不能换一个男生，具体跟匈牙利算法类似。

如果都不行，那么记录一下这个女生希望的最大值，与能匹配到的最大值的差的最小值 delta，在下面的处理中，把这次搜索过的女生的期望都减去 delta，搜索过男生的期望都增加 delta，最后输出每一个 w[match[i]][i] 的和即为最终答案。

注意要先把女生的期望赋值成最大的边，男生的期望赋值为 0。

最后就算出最好能匹配多少，详细的证明可以去问度娘(本人太菜不会)。

总代码：

#include

#define re register

#define inf INT_MAX

using namespace std;

inline int read(){

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}

while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}

return x*f;

}

inline void print(int x){

if(x/10) print(x/10);

putchar(x%10+'0');

}

const int M = 100;

int zuo[M],you[M],w[M][M],a[M][M],b[M][M],match[M],vis1[M],vis2[M];

int n,delta;

bool check(int u){

vis1[u] = 1;

for(re int i(1) ; i<=n ; ++i){

if(vis2[i]) continue;

if(zuo[u]+you[i] == w[u][i]){

vis2[i] = 1;

if(!match[i] || check(match[i])){

match[i] = u;

return 1;

}

}

else delta = min(delta,zuo[u]+you[i]-w[u][i]);

}

return 0;

}

inline void KM(){

for(re int i(1) ; i<=n ; ++i){

you[i] = 0,zuo[i] = -inf;

for(re int j(1) ; j<=n ; ++j) zuo[i] = max(zuo[i],w[i][j]);

}

for(re int i(1) ; i<=n ; ++i){

while(1){

memset(vis1,0,sizeof(vis1));

memset(vis2,0,sizeof(vis2));

delta = inf;

if(check(i)) break;

for(re int j(1) ; j<=n ; ++j){

if(vis1[j]) zuo[j]-=delta;

if(vis2[j]) you[j]+=delta;

}

}

}

int ans=0;

for(re int i(1) ; i<=n ; ++i) ans += w[match[i]][i];

printf("%d",ans);

}

signed main(){

n=read();

for(re int i(1) ; i<=n ; ++i) for(re int j(1) ; j<=n ; ++j) a[i][j] = read();

for(re int i(1) ; i<=n ; ++i) for(re int j(1) ; j<=n ; ++j) b[i][j] = read();

for(re int i(1) ; i<=n ; ++i) for(re int j(1) ; j<=n ; ++j) w[i][j] = a[i][j]*b[j][i];

KM();

return 0;

}