首页 > 其他分享 >解决一般图最大匹配的利器——带花树浅析

解决一般图最大匹配的利器——带花树浅析

时间:2023-05-02 12:22:24浏览次数:50  
标签:花树 pre 匹配 增广 int 利器 fa 浅析 match

Preface

好像很久没有学过新算法了罢,或者说没有写过板子的博客了

前段时间在DS专题中可能有学过吉司机线段树,不过由于那个重在思想而且最关键的复杂度证明不太懂也就没有专门写篇博客了

这次在图论专题中补上了OI时一直没学的带花树,不过好像这个科技现在除了做板子题外还没什么太大的用处的说

个人学习自某dalao的Blog,感觉讲的十分清晰易懂,狠狠地好评


前置知识

在二分图的匈牙利算法中,其核心就是寻找尽可能多的增广路过程,这里我们系统性的给出一些概念的定义

  • 孤立点:指一个\(u\),没有与其匹配的点\(v\)
  • 交错路(alternating path),指一条图中的路径,满足上面的边在匹配中交替出现
  • 增广路(augmenting path),指一条开始并结束于不相同的孤立点的交错路

由于增广路的定义,上面不是匹配的边比是匹配的边多,因此增广路的边条数为奇数

而如果图中没有增广路了,则我们找到了一个最大匹配;否则我们通过增广操作一定可以获得更大的匹配

因此不管是二分图还是一般图,找最大匹配算法的核心都是一直执行增广操作直至不能再增广


关于花的思考

关于花的定义

带花树的核心,莫过于其独特的缩环为花的操作,我们先给出形式化的花的定义:

一朵花\(B\)是图\(G\)中的一个包含\(2k+1\)个点的奇环,其中\(k\)条边在匹配\(M\)中,并存在从环上任意一点\(v\)(也叫花根)到某个孤立点\(w\)的交错路(也叫花茎

然后我们就可以定义图\(G'\)为将花\(B\)缩为点后的新图,\(M'\)为此时\(G'\)中的匹配

不难发现\(G'\)中含有\(M'\)的增广路当且仅当\(G\)中含有\(M\)的增广路,且\(M'\)在图\(G'\)中的增广路\(P'\)可以通过展开收缩的花来还原得到\(G\)中的匹配\(M\)

如何找到图中的花

  1. 从一个孤立的点\(w\)开始遍历图
  2. 从孤立点\(w\)开始遍历,并标记\(w\)为o型点(out of M)
  3. 交替地用i和o标记结点,保证无两个相邻结点有相同标记
  4. 如果找到两个相邻结点均含有标记o,那么我们就找到了一个奇环与一朵花

关于花的一些细节

关于前面提到的新图和原图的增广路等价,形式化的表示就是如果在\(P'\)中存在一条\(u\to V_B\to w\)的增广路,这条增广路在原图中可以被替换为\(u\to (u’\to\ldots\to w’)\to w\),其中\(u',w'\)在花\(B\)中

而与此同时\(u'\to w'\)的选择必须保证此时新增广路仍然是交替匹配的,这个用图会比较好理解:

还有一种比较特殊的情况就是当\(P'\)在\(V_B\)结束时,我们就要把这条增广路替换为\(u\to(u’\to\ldots\to v’)\),其中\(u',v'\)在花\(B\)中

而与此同时\(u'\to v'\)的选择必须保证此时新增广路仍然是交替匹配的,还是一图胜千言:

因此不论对于哪种情况,把奇环缩成点都能对应处理,这便是带花树算法的核心

一些思考

为什么只考虑缩奇环而不缩偶环,因为偶环的标记是不会发生冲突的

即可以从某个点出发,对一个偶环上的点全部匹配后回到原点,这显然是最优的

而实现的时候我们不需要真正实现缩花的过程,而是隐式地只记录每个点属于哪个花即可


具体实现

我们对于每个点维护以下信息:

  • \(type\),表示这个点的类型,\(0\)为o类点,\(1\)为i类点,\(-1\)为未访问
  • \(match\),表示这个点匹配的点,注意\(match\)具有双向性,即若\(match[x]=y\),则必有\(match[y]=x\)
  • \(pre\),表示这个点在交错路上相邻但不和当前点构成匹配的点,注意\(pre\)在非花的增广路上是单向的,不过由于在花上增广的方向不定,因此\(pre\)是双向的
  • \(father\),表示这个点所属的花,若不属于任何花则置为本身

然后算法的大致过程如下:

  1. 若寻找到一个未被标记的未匹配点:将其标记为i型点,找到一条增广路,更新并维护该增广路的信息,完成增广
  2. 若寻找到一个未被标记的点,但其已经被匹配,将其标记为i型点,并将其匹配的点标记为o型点,加入队列
  3. 若寻找到一个已经被标记的i型点,说明此时构成偶环,直接无视
  4. 若寻找到一个已经被标记的o型点,说明此时构成奇环且构成花,在当前扩展出的交错路上找到其公共祖先\(lca\),\(lca\)此时为花根,沿着两侧的花边爬到花根,将路径上的结点的\(father\)指针更新,标记全部更新为o,并将\(pre\)指针变为双向指针

板子

模板题见:Luogu P6113 【模板】一般图最大匹配

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,m,x,y,match[N],ans; vector <int> v[N];
namespace Blossom_Algorithm
{
	int fa[N],vis[N],pre[N],tp[N]; queue <int> q;
	inline int getLCA(int x,int y)
	{
		static int idx=0; ++idx; x=fa[x]; y=fa[y];
		while (vis[x]!=idx)
		{
			if (x) vis[x]=idx,x=fa[pre[match[x]]];
			swap(x,y);
		}
		return x;
	}
	inline void blossom(int x,int y,int lca)
	{
		while (fa[x]!=lca)
		{
			pre[x]=y; y=match[x];
			if (tp[y]==1) tp[y]=0,q.push(y);
			fa[x]=fa[y]=fa[lca]; x=pre[y];
		}
	}
	inline bool Augument(CI s)
	{
		for (RI i=1;i<=n;++i) fa[i]=i;
		memset(tp,-1,sizeof(tp)); q=queue <int>();
		q.push(s); tp[s]=0; while (!q.empty())
		{
			int now=q.front(); q.pop();
			for (int to:v[now]) if (!~tp[to])
			{
				if (pre[to]=now,tp[to]=1,!match[to])
				{
					for (int x=now,y=to;y;x=pre[y])
					match[y]=x,swap(match[x],y);
					return 1;
				}
				tp[match[to]]=0; q.push(match[to]);
			} else if (!tp[to]&&fa[now]!=fa[to])
			{
				int lca=getLCA(now,to);
				blossom(now,to,lca); blossom(to,now,lca);
			}
		}
		return 0;
	}
};
using namespace Blossom_Algorithm;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (i=1;i<=n;++i) if (!match[i]) ans+=Augument(i);
	for (printf("%d\n",ans),i=1;i<=n;++i) printf("%d ",match[i]);
	return 0;
}

Postscript

带花树的复杂度上界在于枚举孤立点时要把所有点入队,如果找到花的话就要遍历整朵花,因此总复杂度为\(O(n^3)\)

而据说带花树还有扩展可以用来解决一般图的带权匹配问题,这个有点恐怖了就先不管了

标签:花树,pre,匹配,增广,int,利器,fa,浅析,match
From: https://www.cnblogs.com/cjjsb/p/17367528.html

相关文章

  • 使用爬虫利器 Playwright,轻松爬取抖查查数据
    使用爬虫利器Playwright,轻松爬取抖查查数据我们先分析登录的接口,其中url有一些非业务参数:ts、he、sign、secret。然后根据这些参数作为关键词,定位到相关的js代码。最后,逐步进行代码的跟踪,发现大部分的代码被混淆加密了。花费了大半天,来还原这些混淆加密的代码,但是也没......
  • 产品质量管理利器,华为云发布CodeArts Defect缺陷管理服务
    摘要:近日,华为云CodeArtsDefect缺陷管理服务正式上线,提供结构化缺陷跟踪流程和标准化的质量度量模型。本文分享自华为云社区《产品质量管理利器,华为云发布CodeArtsDefect缺陷管理服务》,作者:华为云头条。美国管理学家彼得曾经说过,“决定水桶盛水量多少的关键因素不是其最长的板......
  • 一篇文章教你学会数据备份利器rsync
     作为一个系统管理员,数据备份是非常重要的。阿铭有一次没有做好备份策略,结果磁盘坏了,数据全部丢失。所以在以后的系统维护工作中,你一定要时刻牢记给数据做备份。在Linux系统下数据备份的工具很多,但阿铭只用一种,那就是rsync,从字面意思上可以理解为remotesync(远程同步)。rsync不......
  • 浅析低代码开发的典型应用构建场景
    在数字经济蓬勃发展的大势之下,企业软件开发人员供给不足、开发速度慢、开发成本高、数字化和智能化成效不明显等问题日益凸出,阻碍了企业的数字化转型。而近年来,低代码的出现推动了经济社会的全面提效,也成为人才供求矛盾的润滑剂。低代码迎合企业数字化转型需求,一方面降低软件开发......
  • 盘点一款Python发包收包利器——scapy
    今日鸡汤潮平两岸阔,风正一帆悬。    大家好,我是黄伟。今天跟大家讲的是Python用于发送接受网络数据包的模块-------scapy。前言众所周知,我们每天上网都会有很多数据包需要发送,然后处理在接受在发送,这样一个循环往复的过程,这里就显示了很多数据包的发送接收数据。那么,什么是包......
  • 爬虫利器:jsDOM
    之前使用node做爬虫的时候,使用puppeteer来模拟浏览器,然后抓取信息,但是这样的效率和消耗太大了,所以需要一种更为效率的方法:直接使用axios来请求对应的url,然后通过jsDom,渲染成一个虚拟的html然后进行取值。废话不多说直接上代码:先安装jsdomnpmijsdom然后写下面实例化cons......
  • 浅析python中装饰器原理
    一、什么叫装饰器?装饰器(decorator)的本质是一个函数,它接收一个函数作为参数,并返回一个被装饰过后的函数二、装饰器的作用?在不修改被修饰过函数的代码和和调用方式的情况下,给被装饰函数增加额外的功能三、装饰器的应用场景?插入日志、性能测试、事务处理、缓存、权限校验等场景......
  • 若依RuoYi框架浅析 基础篇①——日志logs本地保存
    文章目录日志保存位置在/home/ruoyi/logs/[root@iZ2ze30dygwd6yh7gu6lskZlogs]#cd/home/ruoyi/logs/[root@iZ2ze30dygwd6yh7gu6lskZlogs]#lssys-error.2021-02-28.logsys-error.logsys-info.2021-02-28.logsys-info.2021-03-01.logsys-info.logsys-user.2021-0......
  • 浅析流媒体技术的发展趋势及EasyCVR视频技术的应用
    随着科技的不断发展,流媒体已经成为人们日常生活中必不可少的一部分。为了进一步提高流媒体的质量,未来的技术革新方向将集中在以下几个方面:1)提高视频编解码技术的质量和效率随着高清视频的普及,人们对流媒体的质量要求越来越高。未来的技术革新方向将重点关注如何提高视频编解码技......
  • 浅析Spring Security 核心组件
    前言近几天在网上找了一个SpringSecurity和JWT的例子来学习,项目地址是:github.com/szerhusenBC…作为学习SpringSecurity还是不错的,通过研究该demo发现自己对SpringSecurity一知半解,并没有弄清楚SpringSeurity的流程,所以才想写一篇文章先来分析分析SpringSecurity的......