[hdu2255]奔小康赚大钱(二分图最优匹配、KM算法)
2024-08-23 08:04:32
题目大意:求二分图的最优匹配(首先数目最大, 其次权值最大)。
解题关键:KM算法
复杂度:$O(n^3)$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=;
const int inf=0x3f3f3f3f;
int nx,ny;
int g[N][N];
int match[N],lx[N],ly[N];//y中各点匹配状态,x,y中的顶点标号
int slack[N];
bool visx[N],visy[N]; bool hungry(int x){
visx[x]=;
for(int y=; y<=ny; y++){
if(visy[y])continue;
int tmp=lx[x]+ly[y]-g[x][y];
if(tmp==){
visy[y]=true;
if(match[y]==- ||hungry(match[y])){
match[y]=x;
return ;
}
}
else if(slack[y]>tmp) slack[y]=tmp;
}
return ;
} int KM(){
memset(match, -, sizeof match);
memset(ly, , sizeof ly);
for(int i=;i<=nx;i++){
lx[i]=-inf;
for(int j=;j<=ny;j++) lx[i]=max(lx[i],g[i][j]);
}
for(int x=;x<=nx;x++){
for(int i=;i<=ny;i++) slack[i]=inf;
while(){
memset(visx,,sizeof visx);
memset(visy,,sizeof visy);
if(hungry(x))break;
int d=inf;
for(int i=;i<=ny;i++)if(!visy[i]&&d>slack[i]) d=slack[i];
for(int i=;i<=nx;i++)if(visx[i])lx[i]-=d;
for(int i=;i<=ny;i++){
if(visy[i])ly[i]+=d;
else slack[i]-=d;
}
}
}
int res=;
for(int i=;i<=ny;i++)
if(match[i]!=-) res+=g[match[i]][i];
return res;
} int main(){
int n;
while(~scanf("%d",&n)){
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&g[i][j]);
nx=ny=n;
printf("%d\n",KM());
}
return ;
}
最新文章
- js之事件冒泡和事件捕获详细介绍
- UID 修改 &; UID 锁死修复
- WP8_ListBox的用法
- Aspose.cell.dll的使用,导excel表
- ORACLE解锁record is locked by another user
- Matlab 之 im2col
- window对象细节(转载)
- OC-变量和数据类型
- RedHat9.0下载地址
- Openjudge-NOI题库-出书最多
- Linux MTD子系统 _从模型分析到Flash驱动模板
- .NET Core 使用RSA算法 加密/解密/签名/验证签名
- python学习笔记 list
- Oracle Metalink Notes Collection
- HTML基础-标签
- Handler基本运行机制
- 关于Unity中GrabPass截屏的使用和Shader的组织优化
- Python学习-34.Python中os模块的一些方法(二)
- android 仿网易新闻首页框架
- SQLite 使用技巧
热门文章
- hdu 5243 Homework
- 浅谈 C# CLR 执行模块
- C++Builder XE5对于C++11的支持真蛋疼
- LeetCode OJ:Binary Tree Paths(二叉树路径)
- uva11997 K Smallest Sums&;&;UVALive 3135 Argus(优先队列,多路归并)
- CI框架后台添加左侧导航栏出现的一系列问题
- Arc083_F Collecting Balls
- Swap Adjacent Elements
- Redis底层探秘(一):简单动态字符串(SDS)
- C#进阶之路(五):Linq初识