[学习笔记]最小割之最小点权覆盖&&最大点权独立集
2024-09-02 09:14:34
最小点权覆盖
给出一个二分图,每个点有一个非负点权
要求选出一些点构成一个覆盖,问点权最小是多少
建模:
S到左部点,容量为点权
右部点到T,容量为点权
左部点到右部点的边,容量inf
求最小割即可。
证明:
每一个割集,对应选择一些点,对应一个覆盖。
每个覆盖有不同的代价,选择最小的就是最小点覆盖
每个割集有不同的代价,选择最小的就是最小割
由于割集和覆盖一一对应
所以,这个新图的最小割,就对应原图的最小点覆盖。
最大点权独立集
给出一个二分图,每个点有一个非负点权
要求选出一些点构成一个独立集,问点权最大是多少
建模:
等于:总权值-最小点权覆盖
证明:
扔掉覆盖的点的剩余点一定是一个独立集
而且,根据覆盖=点数-独立集
对于一个固定的点覆盖,独立集已经不能更大。
所以,一个固定的点覆盖下,最大独立集是确定的。两者呈现一一对应的关系。
而总权值不变,所以选择扔掉的覆盖集总权值最小即可。
所以,最大点权独立集=总权值-最小点权覆盖
例题:
方格取数问题
在一个有m*n 个方格的棋盘中
每个方格中有一个正整数
现要从方格中取数,使任意2 个数所在方格没有公共边
求取出的数的总和最大是多少。
题解:
将棋盘国际象棋黑白染色
然后连边
然后最大点权独立集即可。
最新文章
- java并发编程(十三)经典问题生产者消费者问题
- JDBC删除表数据
- ORACLE RAC 下非缺省端口监听配置(listener.ora tnsnames.ora)
- 为什么乱码:<;meta http-equiv=";content-type";>;前的非ANSI字符
- 八位彻底改变App Store的iOS开发者
- Jquery库及其他库之间的$命名冲突解决办法
- linux编译相关知识
- 移动Web开发图片自适应两种常见情况解决方案
- WCF - 契约
- 平方和与立方和 AC 杭电
- iOS 导航条的影响
- 一步一步的理解C++STL迭代器
- FFT学习笔记
- RemindMe
- 贪心,打表(或者快速幂), UVA - 11636
- 电子表格Excel
- SpringBoot结合swagger2快速生成简单的接口文档
- Kubernetes 存储系统 Storage 介绍
- Linux 下 CPU 使用率与机器负载的关系与区别
- struts2 资源国际化