首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

二分图最大权完美匹配

编程知识
2024年09月13日 14:05

问题

给定一个二分图,左部有 \(n\) 个点,右部有 \(m\) 个点,边 \((u_i, v_j)\) 的边权为 \(A_{i,j}\)。求该二分图的最大权完美匹配。

转化

问题可以写成线性规划的形式,设 \(f_{i, j}\) 表示匹配中是否有边 \((u_i, v_j)\),求

\[\begin{gather*} \text{maximize} \quad & \sum_{i=1}^n \sum_{j=1}^m f_{i, j} \times A_{i, j} \\ \text{subject to} \quad & \sum_{i=1}^n f_{i, j} = 1 \quad \forall j \in [1, m] \\ & \sum_{j=1}^m f_{i,j}=1\quad\forall i \in [1, n] \\ & f_{i,j} \ge 0 \quad\forall i, j \end{gather*} \]

转为对偶问题:

\[\begin{gather*} \text{minimize} \quad & \sum_{i=1}^n hu_i + \sum_{j=1}^m hv_i \\ \text{subject to} \quad & hu_i + hv_i \ge A_{i,j} \quad\forall i, j \end{gather*} \]

在这个问题中,\(hu\)\(hv\) 又称作“顶标”。

分析

根据互补松弛定理,如果 \(f_{i,j}=1\),则有 \(hu_i+hv_j=A_{i,j}\)。这给出了判定一组顶标是否最优的方式:

一组顶标 \(hu, hv\) 最优,当且仅当子图 \(H = \left\{(i, j) \mid hu_i + hv_j = A_{i,j}\right\}\) 存在完美匹配。

做法

首先给出一个满足 \(hu_i+hv_j \ge A_{i,j}\) 的顶标(不一定最优)(例如,令 \(hu_i = hv_j = +\infty\)),并维护对应的匹配。然后尝试在不破坏条件的情况下修改顶标,使得匹配可以被增广。

具体而言,遍历 \(i\)\(1\)\(n\),每次尝试将 \(i\) 加入到匹配中(类似于求二分图最大匹配的匈牙利算法)。我们可以求出\(i\) 为根的交错树,如果已经存在增广路,那么直接增广便是,否则我们需要修改顶标来使交错树生长。设交错树中的左部点集为 \(S\),右部点集为 \(T\),那么必有 \(|S| = |T| + 1\)(交错树的性质)。令 \(\Delta = \min\{hu_i + hv_j - A_{i,j} \mid i \in S \land j \notin T\}\),那么将 \(S\) 中的点顶标减去 \(\Delta\),将 \(T\) 中的点顶标加上 \(\Delta\),可以验证得到的新的顶标依然满足 \(hu_i+hv_j \ge A_{i,j}\) 的限制,且原图中的匹配一定包含于对应的新图 \(H'\) 中,此外,新图中至少增加了一条边,这使得我们的交错树可以继续生长,直到找到增广路为止。

代码(洛谷 P6577

#define DEBUG 0
#include <cstdio>
#include <cassert>
#include <vector>
template <class T> using Arr = std::vector<T>;
#define int long long
const int INF = 1e8;

signed main() {
	int n, m;
	scanf("%lld%lld", &n, &m);
	struct edge_t {
		int v, w;
	};
	Arr<Arr<edge_t>> e(2 * n);
	for (int i = 0; i < m; ++i) {
		int l, r, w;
		scanf("%lld%lld%lld", &l, &r, &w);
		--l; r += n - 1;
		e[l].push_back({r, w});
		e[r].push_back({l, w});
	}

	Arr<int> match(2 * n, -1), h(2 * n, INF);
	for (int i = 0; i < n; ++i) {
		Arr<int> vis(2 * n, false);    // 是否在当前求出的交错树中,即 $S \cup T$ 
		Arr<int> upd(2 * n, n * INF);  // 最小的 Δ 值                             
		Arr<int> from(2 * n, -1);      // 维护增广路所用,即交错树上的父亲        
		int p = i;
		vis[p] = true;
		int d, dp;  // Δ 及其对应的 j
		while (true) {
			d = n * INF, dp = -1;

			// 求出 Δ
			for (auto [to, w] : e[p])
				if (!vis[to]) {
					int delta = h[p] + h[to] - w;
					if (delta < upd[to])
						upd[to] = delta, from[to] = p;
				}
			for (int j = n; j < 2 * n; ++j)
				if (!vis[j] && upd[j] < d && from[j] != -1)
					d = upd[j], dp = j;
			assert(~dp);


			// 修改顶标
			h[i] -= d;
			for (int j = n; j < 2 * n; ++j)
				if (vis[j])
					h[j] += d, h[match[j]] -= d;
				else
					upd[j] -= d;

			// 找到增广路
			if (match[dp] == -1)
				break;

			// 生长交错树
			vis[dp] = true;
			vis[match[dp]] = true;
			p = match[dp];
		}

		// 增广
		while (~dp) {
			match[dp] = from[dp];
			int tmp = match[from[dp]];
			match[from[dp]] = dp;
			dp = tmp;
		}
	}

	long long ans = 0;
	for (int i = 0; i < 2 * n; ++i)
		ans += h[i];
	printf("%lld\n", ans);
	for (int i = n; i < 2 * n; ++i)
		printf("%lld ", match[i] + 1);
	puts("");
	return 0;
}

参考资料

From:https://www.cnblogs.com/0x1B/p/18412112
本文地址: http://www.shuzixingkong.net/article/1983
0评论
提交 加载更多评论
其他文章 经典前端+后端+表头+表身的开发实战参考简易模板【珍藏】
前端部分(Vue 3 + Element Plus) 1. 修改 MPS002HList.vue(主生产计划列表) a. 添加查询表单 在模板中添加查询表单,包含产品料号、品名、规格和年月的输入项。 &lt;template&gt; &lt;div&gt; &lt;!-- 查询表单 --&gt; &
面试官:线程池遇到未处理的异常会崩溃吗?
首先,这个问题考察的是你对线程池 execute 方法和 submit 方法的理解,在 Java 线程池的使用中,我们可以通过 execute 方法或 submit 方法给线程池添加任务,但如果线程池中的程序在执行时,遇到了未处理的异常会怎么呢?接下来我们一起来看。 1.execute方法 exec
面试官:线程池遇到未处理的异常会崩溃吗? 面试官:线程池遇到未处理的异常会崩溃吗?
支付宝携手HarmonyOS SDK打造高效便捷的扫码支付体验
背景 在日常的购物转账、生活缴费等在线支付中,用户在正式拉起支付界面前,均需要至少经历一次&quot;识别&quot;+两次&quot;寻找&quot;,即识别归属应用、寻找应用、寻找扫码入口,才能完成扫码、付款,每一步都带来不同程度的用户流失。如何将步骤繁琐的扫码支付做到最简化,是优化在线支付体验
支付宝携手HarmonyOS SDK打造高效便捷的扫码支付体验 支付宝携手HarmonyOS SDK打造高效便捷的扫码支付体验 支付宝携手HarmonyOS SDK打造高效便捷的扫码支付体验
常回家看看之house_of_emma
house_of_emma 前言: 相比较于house_of_kiwi(house_of_kiwi),house_of_emma的手法更加***钻,而且威力更大,条件比较宽松,只需要lagebin_attack即可完成。 当然把两着放到一起是因为它们都利用了__malloc_assest来刷新IO流
常回家看看之house_of_emma 常回家看看之house_of_emma 常回家看看之house_of_emma
Linux下Shell脚本实现统一管理服务启停重启
公司今年开始了大批量的裁员,人心惶惶,所以强迫自己学习点新知识,刚好领导给找了个事情,让写个脚本实现一键启停Linux服务器上的服务,于是开始研究这个怎么搞。 最开始的时候,有点想当然了,觉得一键启停不就是写个菜单,调用一下服务启动停止的命令就可以实现,但是在写的过程中,发现全是坑,搞的心态都崩了,
架构师备考的一些思考(四)
前言 对于数学,我们之前学的是对的,但不是真的,所以我们没有数学思维。 对于计算机,我们学校教的是对的,但不是真的,所以仅仅从学校学习知识的应届毕业生,不论985,211,本科,专科都一样,都是一张白纸,啥也不会。 案例分析 案例分析是5选3,第一题必答。 问题一的类型 架构风格对比 问题二的类型
架构师备考的一些思考(四)
Python网页应用开发神器Dash 2.18.1稳定版本来啦
本文示例代码已上传至我的Github仓库:https://github.com/CNFeffery/dash-master Gitee同步仓库地址:https://gitee.com/cnfeffery/dash-master 大家好我是费老师,上周Dash发布了2.18.0新版本,并于今天发布了可
Python网页应用开发神器Dash 2.18.1稳定版本来啦 Python网页应用开发神器Dash 2.18.1稳定版本来啦 Python网页应用开发神器Dash 2.18.1稳定版本来啦
吊打面试官!从多维度理解架构
大家好,我是汤师爷~ 在工作当中,我们经常会听到以下说法: 产品负责人说,现在的业务架构太复杂,需要仔细梳理下。 技术领导说,这个项目很复杂,需要做下系统架构方案评审。 研发经理说,这次秒杀活动访问量非常大,需要用到高并发架构方案。 一线研发说,互联网大厂都会用到微服务架构,我要学学微服务架构设计。
吊打面试官!从多维度理解架构 吊打面试官!从多维度理解架构 吊打面试官!从多维度理解架构