HDU 2255 奔小康,赚钱(KM算法模板)
2023-09-14 09:10:12 时间
解决问题的思路:
二部图,正确的匹配,卡费用流,使用KM算法。
#include <cstring> #include <algorithm> #include <cstdio> #include <iostream> using namespace std; /* KM算法 * 复杂度O(nx*nx*ny) * 求最大权匹配 * 若求最小权匹配。可将权值取相反数,结果取相反数 * 点的编号从0開始 */ const int MAXN = 310; const int INF = 0x3f3f3f3f; int nx,ny;//两边的点数 int g[MAXN][MAXN];//二分图描写叙述 int linker[MAXN],lx[MAXN],ly[MAXN];//y中各点匹配状态。x,y中的点标号 int slack[MAXN]; bool visx[MAXN],visy[MAXN]; bool DFS(int x) { visx[x] = true; for(int y = 0; y < ny; y++) { if(visy[y])continue; int tmp = lx[x] + ly[y] - g[x][y]; if(tmp == 0) { visy[y] = true; if(linker[y] == -1 || DFS(linker[y])) { linker[y] = x; return true; } } else if(slack[y] > tmp) slack[y] = tmp; } return false; } int KM() { memset(linker,-1,sizeof(linker)); memset(ly,0,sizeof(ly)); for(int i = 0;i < nx;i++) { lx[i] = -INF; for(int j = 0;j < ny;j++) if(g[i][j] > lx[i]) lx[i] = g[i][j]; } for(int x = 0;x < nx;x++) { for(int i = 0;i < ny;i++) slack[i] = INF; while(true) { memset(visx,false,sizeof(visx)); memset(visy,false,sizeof(visy)); if(DFS(x))break; int d = INF; for(int i = 0;i < ny;i++) if(!visy[i] && d > slack[i]) d = slack[i]; for(int i = 0;i < nx;i++) if(visx[i]) lx[i] -= d; for(int i = 0;i < ny;i++) { if(visy[i])ly[i] += d; else slack[i] -= d; } } } int res = 0; for(int i = 0;i < ny;i++) if(linker[i] != -1) res += g[linker[i]][i]; return res; } int main() { int n; while(scanf("%d",&n) == 1) { for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) scanf("%d",&g[i][j]); nx = ny = n; printf("%d\n",KM()); } return 0; }
相关文章
- Cloud Studio高阶玩家:强大的YAML模板
- Vue的基本模板
- 学习zencart模板制作[通俗易懂]
- 二分匹配 匈牙利算法 模板-------------------C语言——菜鸟级
- 【c++】【基础】【primer_plus】【第八章】 引用与模板函数
- 【Linux + Makefile】简单实用的Makefile模板来了
- C++ STL 标准模板库(排序/集合/适配器)算法
- C++ STL 标准模板库(非变易/变易)算法
- 后端思维篇:如何抽个通用上报模板
- 设计模式 | 行为型 | 模板方法模式
- SMW0上传EXCEL模板时报错无分配给对象***的MIME类型详解编程语言
- Linux简历模板:快速定制个性化的简历(linux简历模板)
- ASPCrazy模版操作类(最简单的模板类、仅提供交流)
- 最小树形图模板朱刘算法分享
- 排序算法模板实现示例分享
- ThinkPHP模板判断输出Empty标签用法详解
- PHP针对常规模板引擎中与CSS/JSON冲突的解决方法