草庐IT

最小割树学习笔记

Xie Zheyuan 2023-03-28 原文

前言

最小割树（Gomory-Hu Tree）通过分治的思想，将图中的最小割关系建成一棵带权了树上问题。它的主要用途是求解全源最小割 / 最大流。

前置知识：

  • 一种快速的最大流算法（Dinic/ISAP 均可，FF/EK 不行，HLPP 虽然快但不方便求最小割树），本文中采用 Dinic。
  • 最小割最大流定理：最小割=最大流
  • 分治思想

下文中若无例外，均用 \(O(\text{maxflow}(n,m))\) 表示求一个 \(n\) 个点 \(m\) 条边的图上任意两点之间的最大流 / 最小割的时间复杂度。

建立

首先我们将全图看成一个集合。然后我们任选两个点 \(s,t\) 跑一遍最大流。

然后你会发现，我们可以通过源点是否与其连通分成两个集合一条权为最大流流量的边。

然后将两个集合分治，重复上述操作，直到只剩下一个点为止。

这样子我们就建出了一个最小割树（因为本来一个节点的所有子树就互不连通，所以这一定是一棵树）。

（但是我们一般都不把这棵树真的建出来，为什么呢，请看下文）。

性质

最小割树的重要性质：任意两个点的最小割等于这两个点在最小割树上的路径上的最小值。

为什么呢？因为我们的最小割树的最小割和原来的图的最小割是等价的（因为我们建树的时候就是按照最小割性质建的）而树上最小割显然是路径最小值。

于是读者可能会考虑使用 倍增 / 树链剖分去解决。但是由于最大流复杂度本身过大，因此我们甚至可以暴力算出全源最小割，最后 \(O(1)\) 回答询问。

具体来说，分治时跨集合的两个点 \(u,v\) 的最小割 \(i(u,v)\) （也就是路径最小值）可以在心中脑补出来。它只和三部分有关：\(u\to s,s\to t,t\to v\)（出来，跨子树代价，进去）。我们对这三部分的最小割取最小值即可。

代码实现

重要的事情说三遍：注意退流！注意退流！注意退流！。

void GomoryHu(int l,int r){
	if(l==r) return;
	S=node[l],T=node[l+1];
	int t=maxflow(),ss=node[l],tt=node[l+1];
	ans[S][T]=ans[T][S]=t;
	int ltot=0,rtot=0;
	for(int i=l;i<=r;i++){
		if(dep[node[i]]) tl[++ltot]=node[i];
		else tr[++rtot]=node[i];
	}
	for(int i=1;i<=ltot;i++) node[i+l-1]=tl[i];
	for(int i=1;i<=rtot;i++) node[ltot+l+i-1]=tr[i];
	GomoryHu(l,l+ltot-1);
	GomoryHu(l+ltot,r);
	for(int i=1;i<=ltot;i++){
		for(int j=1;j<=rtot;j++){
			int ii=node[i+l-1],jj=node[j+ltot+l-1];
			ans[ii][jj]=ans[jj][ii]=min(min(ans[ii][ss],ans[ss][tt]),ans[tt][jj]);
		}
	}
}

课后习题

P4897 【模板】最小割树（Gomory-Hu Tree）

给出 \(n+1\) 个点和 \(m\) 条边的 无向图，\(Q\) 组询问，每组询问给出两个点，求两点之间的最小割。

\(1 \leq n \leq 500,1 \leq m \leq 1500,1 \leq Q \leq 10^5\)

P3329 [ZJOI2011]最小割

\(T\) 组数据，每组数据给出 \(n\) 个点和 \(m\) 条边的有向图，\(q\) 组询问，每组询问一个 \(x\)，求出有多少对点满足最小割小于等于 \(x\)。在两组测试数据之间需要输出一行空行。

\(1 \leq T \leq 10\)，\(1 \leq n \leq 150\)，\(0 \leq m \leq 3000\)，\(0 \leq x \leq 2^{31}-1\)，\(0 \leq q \leq 30\)

P4123 [CQOI2016]不同的最小割

给出 \(N\) 个点 \(M\) 条边的有向图，求任意两点的最小割有多少种。

\(1\leq N\leq 850,1\leq M\leq 8500\)

笔记最小spaninlineclass算法与数据结构

有关最小割树学习笔记的更多相关文章

  1. LC滤波器设计学习笔记（一）滤波电路入门 - 2

    目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称

  2. CAN协议的学习与理解 - 2

    最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总

  3. 深度学习部署：Windows安装pycocotools报错解决方法 - 2

    深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal

  4. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  5. ruby - 我正在学习编程并选择了 Ruby。我应该升级到 Ruby 1.9 吗？ - 2

    我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or

  6. ruby - 我如何学习 ruby​​ 的正则表达式？ - 2

    如何学习ruby​​的正则表达式？(对于假人) 最佳答案 http://www.rubular.com/在Ruby中使用正则表达式时是一个很棒的工具，因为它可以立即将结果可视化。 关于ruby-我如何学习ruby​​的正则表达式？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1881231/

  7. 深度学习12. CNN经典网络 VGG16 - 2

    深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG

  8. 机器学习——时间序列ARIMA模型(四)：自相关函数ACF和偏自相关函数PACF用于判断ARIMA模型中p、q参数取值 - 2

    文章目录1、自相关函数ACF2、偏自相关函数PACF3、ARIMA(p,d,q)的阶数判断4、代码实现1、引入所需依赖2、数据读取与处理3、一阶差分与绘图4、ACF5、PACF1、自相关函数ACF自相关函数反映了同一序列在不同时序的取值之间的相关性。公式：ACF(k)=ρk=Cov(yt,yt−k)Var(yt)ACF(k)=\rho_{k}=\frac{Cov(y_{t},y_{t-k})}{Var(y_{t})}ACF(k)=ρk​=Var(yt​)Cov(yt​,yt−k​)​其中分子用于求协方差矩阵，分母用于计算样本方差。求出的ACF值为[-1,1]。但对于一个平稳的AR模型，求出其滞

  9. Unity Shader 学习笔记（5）Shader变体、Shader属性定义技巧、自定义材质面板 - 2

    写在之前Shader变体、Shader属性定义技巧、自定义材质面板，这三个知识点任何一个单拿出来都是一套知识体系，不能一概而论，本文章目的在于将学习和实际工作中遇见的问题进行总结，类似于网络笔记之用，方便后续回顾查看，如有以偏概全、不祥不尽之处，还望海涵。1、Shader变体先看一段代码......Properties{ [KeywordEnum(on,off)]USL_USE_COL("IsUseColorMixTex?",int)=0 [Toggle(IS_RED_ON)]_IsRed("IsRed?",int)=0}......//中间省略，后续会有完整代码 #pragmamulti_c

  10. Tcl脚本入门笔记详解（一） - 2

    TCL脚本语言简介•TCL（ToolCommandLanguage）是一种解释执行的脚本语言（ScriptingLanguage）,它提供了通用的编程能力：支持变量、过程和控制结构；同时TCL还拥有一个功能强大的固有的核心命令集。TCL经常被用于快速原型开发，脚本编程，GUI和测试等方面。•实际上包含了两个部分：一个语言和一个库。首先，Tcl是一种简单的脚本语言，主要使用于发布命令给一些互交程序如文本编辑器、调试器和shell。由于TCL的解释器是用C\C++语言的过程库实现的，因此在某种意义上我们又可以把TCL看作C库，这个库中有丰富的用于扩展TCL命令的C\C++过程和函数，所以，Tcl是

随机推荐