系列trick - 建图
对偶图
主体思想：平面图的割，等价于对偶图的路
网上有114514篇题解，这里不赘述
点变边
主体思想：点带点权，而要在点上实现一些在边上的问题，比如最小割点，将点 \(P\) 拆成 \(P_i\) 和 \(P_o\)，在 \(P_i\) 和 \(P_o\) 之间连边 \(val_P\)，即可转化成边权。
例题：[BJOI2016]水晶
枚举三个不合法的点，用这个 trick 做最小割点就可以了。
网络流 - 割意义
主体思想：“割”表示“不选”，用它来实现一些例如“必须同时选”，“不能怎么样选”的问题，通常是从反面用割维护不合法的，然后总和-割，得到答案。
经典例题：最大权闭合子图
你有一个图，在这个图中选择一个子图，使得子图中每一个点的出边连向的点也都包含在子图中，称这个子图为“闭合子图”
每个点带一个权，可能是负的。找到最大权闭合子图。
把正的接 \(S\)，负的接 \(T\)，边容量为点权绝对值。原图中的边直接连，容量为 \(INF\) （相当于禁止这条边被割掉）
用正权和-最小割，就是最大权闭合子图。
简单（而不严谨的）证明：
现在我们已证，割只会割 \(S,T\) 接的边。
首先明确什么叫“选了”。对于正权点，割了等价于不选；对于负权点，割了等价于选。原因就是建图的时候我们相当于对负权点的边权变相反数之后再加边，才导致正负有区别。
考虑割 \(S\) 中的边，用正权和-最小割之后，这个操作的意义相当于“不选某个正权点”
同理，割 \(T\) 中的边相当于，（此时我们不会割 \(S\) 中的对应边），选了 \(S\) 中的某些边，而以带上某些负权点问代价。
这显然是原问题的两种决策。接下来我们只需要证明，选出来的割边所对应的点集，一定是闭合权图，即可。
假设现在选了 \(u\)，并且没选 \(u\) 的出边到达的点 \(v\)。考虑 \(4\) 种情况
- \(u+,v+\) ：显然我们一定会选 \(v\)，不会出现这个情况
- \(u+,v-\)：没割 \(u\)，没割 \(v\)，此时 \(S\rightarrow u \rightarrow v\rightarrow T\) 是一条通路，与割的定义矛盾
- \(u-,v+\)：显然一定会选 \(v\)，不会出现这个情况
- \(u-,v-\)：此时一定有一个正权点到 \(u\)的路，尽管 \(u\rightarrow T\) 断了，但是 \(u\rightarrow v\rightarrow T\) 仍然是通路，与割的定义矛盾。
综上，我们一定不会选一个非闭合子图出来。
再综上，我们一定会得到一个最大权闭合子图。
后记：这个trick，对割的基本定义要求理解深刻。
wwq：最基本的还在错，50遍
最新文章
- iOS文档注释
- jquery获取多重input的方式
- HTML 中禁用鼠标右键和不能选中文字
- html checkbox 全选与反选
- 解决 Zabbix agent on [HOSTNAME] is unreachable for 5 minutes
- nodejs的简单服务器程序
- windows phone (17) ManipulationDelta事件
- ValueError: too many values to unpack
- 七、OpenStack—dashboard组件安装
- webform运行时弹出JavaScript的alert窗口
- php获取id
- 玩转 lua in Redis
- [LeetCode] Majority Element II 求大多数之二
- C语言中，int型函数返回值可以为bool型。
- python魔法方法-自定义序列
- cocos2d-x与UIKit混合编程实现半透明效果
- inbox.MoveTo Folder does not move message out of inbox
- 微软BI 之SSRS 系列 - 解决Pie Chart 中控制标签外部显示与标签重叠的问题
- 【Java】通用版URLConnection 带cookie下载PDF等资源文件
- Nexus 安装 使用说明