最小割树(Gomory-Hu Tree)
2024-10-09 06:51:00
当我们遇到这样的问题:
给定一个 \(n\) 个点 \(m\) 条边的无向连通图,多次询问两点之间的最小割
我们通常要用到最小割树。
博客
建树
分治。记录当前点集,然后随便找俩点当 \(s\) 和 \(t\),跑一遍最小割,然后在“最小割树”上把 \(s\) 和 \(t\) 连边,并且根据“属于s的点”还是“属于t的点”将当前点集分为两部分,直到当前点集大小为1为止。
性质
最小割树上的边 \((u, v)\),其权值为原图中 \(u\) 到 \(v\) 的最小割,断开最小割树上的 \((u, v)\),分成的两个连通块分别是原图中跑完最小割后“属于 \(u\) 的点”和“属于 \(v\) 的点”。
原图中 \(u\) 到 \(v\) 的最小割等于最小割树上 \(u\) 到 \(v\) 的最小边权。
容易感性理解。具体证明见:博客
例题
受实力限制,我只做过一些比较水的最小割树的题。最小割树还需深刻理解。
最新文章
- [NHibernate]条件查询Criteria Query
- 搭建java环境
- HDU 5805 NanoApe Loves Sequence (思维题) BestCoder Round #86 1002
- Translation Lookaside Buffer
- wampserver2.5 apache2.4.9:forbidden,本机可以访问,局域网内部能访问。
- ";数学口袋精灵";bug的发现
- 基于PBOC电子钱包的消费过程详解
- Tinyfool的2013年总结————在困惑和挣扎中试图前行
- Django发送带图片和附件的邮件
- php学习之目录
- EclipseIDE--使用整理
- 海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧
- 一个http请求从用户输入网址开始到结束都发生了什么
- 坑 flutter Positioned相关
- 用java生成32位全球唯一的id编号
- 流媒体协议(RTMP、RTSP、UDP、HTTP、MMS)转换小工具(RTSP转成RTMP案例展示)(转)
- 批处理转exe工具(Quick Batch File Compiler )|bat格式化exe
- 基于prometheus监控k8s集群
- 【洛谷】P1357 花园(状压+矩阵快速幂)
- 11-matlba-bellman-ford;地杰斯特拉