UVA11383 Golden Tiger Claw KM算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了UVA11383 Golden Tiger Claw KM算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2587字，纯文字阅读大概需要4分钟。

内容图文

题目链接：[传送门](https://www.luogu.com.cn/problem/UVA11383)

## 分析

这道题乍看上去没有思路，但是我们仔细一想就会发现这道题其实是一个二分图最大匹配的板子

我们可以把这道题想象成将男生和女生之间两两配对，使他们的好感度最大

我们把矩阵中的元素$a[x][y]$看成女生$x$和男生$y$之间的好感度，跑一个KM算法

因为KM算法会维护$ex_{}boy[x] + ex_{}girl[y]>=love[y][x]$，所以最后的结果就是我们想要的

注意有多组数据

## 代码

``` cpp
#include<bits/stdc++.h>
using namespace std;
#define hzoi 0
const int maxn=505;
int love[maxn][maxn];
int ex_girl[maxn],ex_boy[maxn];
bool vis_girl[maxn],vis_boy[maxn];
int match[maxn],slack[maxn];
int n;
bool dfs(int girl){
vis_girl[girl]=1;
for(int boy=1;boy<=n;boy++){
if(vis_boy[boy]) continue;
int gap=ex_girl[girl]+ex_boy[boy]-love[girl][boy];
if(gap==0){
vis_boy[boy]=1;
if(match[boy]==-1 || dfs(match[boy])){
match[boy]=girl;
return 1;
}
} else {
slack[boy]=min(slack[boy],gap);
}
}
return 0;
}
void KM(){
memset(match,-1,sizeof(match));
memset(ex_boy,0,sizeof(ex_boy));
for(int i=1;i<=n;i++){
ex_girl[i]=love[i][1];
for(int j=2;j<=n;j++){
ex_girl[i]=max(love[i][j],ex_girl[i]);
}
}
for(int i=1;i<=n;i++){
memset(slack,0x3f,sizeof(slack));
while(1){
memset(vis_boy,0,sizeof(vis_boy));
memset(vis_girl,0,sizeof(vis_girl));
if(dfs(i)) break;
int d=0x3f3f3f3f;
for(int j=1;j<=n;j++){
if(!vis_boy[j]) d=min(d,slack[j]);
}
for(int j=1;j<=n;j++){
if(vis_girl[j]) ex_girl[j]-=d;
if(vis_boy[j]) ex_boy[j]+=d;
else slack[j]-=d;
}
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(love,0,sizeof(love));
memset(ex_girl,0,sizeof(ex_girl));
memset(ex_boy,0,sizeof(ex_boy));
memset(vis_girl,0,sizeof(vis_girl));
memset(vis_boy,0,sizeof(vis_boy));
memset(match,0x3f,sizeof(match));
memset(slack,-1,sizeof(slack));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&love[i][j]);
}
}
KM();
int ans=0;
for(int i=1;i<=n;i++){
if(i==1) printf("%d",ex_girl[i]);
else printf(" %d",ex_girl[i]);
ans+=ex_girl[i];
}
printf("\n");
for(int i=1;i<=n;i++){
if(i==1) printf("%d",ex_boy[i]);
else printf(" %d",ex_boy[i]);
ans+=ex_boy[i];
}
printf("\n%d\n",ans);
}
return 0;
}
```

 

内容总结

以上是互联网集市为您收集整理的UVA11383 Golden Tiger Claw KM算法全部内容，希望文章能够帮你解决UVA11383 Golden Tiger Claw KM算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---