当前位置: 首页 > news >正文

二分图最大权完美匹配 KM算法

image

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define LL long long
#define N 510
#define INF 1e12
int n,m;
int match[N];//右点匹配了哪个左点
int va[N],vb[N];//标记是否在交替路中
LL la[N],lb[N];//左顶标,右顶标
LL w[N][N],d[N];//维护更新的delta值bool dfs(int x){va[x]=1; //x在交替路中for(int y=1;y<=n;y++){if(!vb[y]){if(la[x]+lb[y]-w[x][y]==0){//相等子图vb[y]=1; //y在交替路中if(!match[y]||dfs(match[y])){match[y]=x; //配对return 1;}}else //不是相等子图则记录最小的d[y]d[y]=min(d[y],la[x]+lb[y]-w[x][y]);}}return 0;
}
LL KM(){//左顶标取i的出边的最大边权for(int i=1;i<=n;i++) la[i]=-INF;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) la[i]=max(la[i],w[i][j]);for(int i=1;i<=n;i++) lb[i]=0;      for(int i=1;i<=n;i++){while(true){//直到左点i找到匹配fill(va+1,va+n+1,0);fill(vb+1,vb+n+1,0);fill(d+1,d+n+1,INF);if(dfs(i))break;LL delta=INF;for(int j=1;j<=n;j++)if(!vb[j])delta=min(delta,d[j]);for(int j=1;j<=n;j++){//修改顶标if(va[j])la[j]-=delta;if(vb[j])lb[j]+=delta;}}}LL res=0;for(int i=1;i<=n;i++)res+=w[match[i]][i];    return res;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) w[i][j]=-INF; for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);w[x][y]=z;}printf("%lld\n",KM());for(int i=1;i<=n;i++) printf("%d ",match[i]);return 0;
}
http://www.hskmm.com/?act=detail&tid=26954

相关文章:

  • 2025.10.8模拟赛
  • Python 中的排序排序函数及区别
  • RL | 速读 IJCAI 2025 的强化学习论文
  • IDM弹窗解决 - -一叶知秋
  • PHP+MySQL开发语言 在线下单订水送水小脚本源码及搭建指南
  • Sliding Window Algorithm
  • 国庆模拟赛总结
  • 深入解析:video-audio-extractor:视频转换为音频
  • 10.8 CSP-JS 模拟赛 T4. discover
  • 20251008 模拟测 总结
  • VuePress v2是否支持Vue2的配置?
  • 新人UP主:晓牛开发者的第一篇自我介绍博客测试发布
  • ubuntu20.04服务器版安装中文输入法分享
  • DeCLIP
  • 19_win11_wsl_linux_配置jdk_mvn
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名CTF资源库需求洞察
  • 计蒜客 A1108 百度地图的实时路况
  • 学生管理系统面向对象问题分析
  • 解码Linux环境搭建
  • dns 委派
  • 几个重要的偏微分方程(二)
  • 如何测试台式机电源
  • 「SCOI2015」小凸解密码题解
  • 2025免费好用的度数符号的神器
  • 折腾笔记[31]-在线转换吉卜力风格图片
  • 2025 风淋室厂家 TOP 品牌推荐排行榜,不锈钢风淋室,防爆风淋室,自动门风淋室,风淋门公司推荐
  • 计算机视觉的现状与未来挑战
  • #20232408 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • reLeetCode 热题 100- 239. 滑动窗口最大值 队列 - MKT
  • 深入解析:三维坐标转换