最大权闭合子图学习笔记
Miko35
·
·
个人记录
以下均认为「收益」为正的贡献，「代价」为负的贡献。
为方便表述，称 b_i=1 的点被选了，反之没被选。
简介
每个点可以选或不选，存在一元/二元/多元的收益/代价，满足特定条件时，可以跑网络流。
模型描述
有向带权图 (V,E)，你可以给点 i 分配布尔权值 b_i\in \{0,1\}。
对于点 u，若 b_u=1 则你获得其点权 a_u 的收益；对于有向边 (u,v,w)\in E，若 b_u=1\land b_v=0，你会付出 w 的代价。
最大化你的贡献。
解法
保留原图中所有的边，新建源点 s 与汇点 t。
对于每个点 i，若 a_i>0 则加入边 (s,i,|a_i|)，否则加入边 (i,t,|a_i|)。
对该图跑最大流，令答案为 ans，则原问题答案为 \left(\sum_{a_i>0}a_i\right)-ans。
正确性
不妨残量网络上，与 s 连通的点集为 S，与 t 连通的点集为 T。断言 \forall i\in S 有 b_i=1，\forall i\in T 有 b_i=0。
则最小割由且仅由三部分组成：
由此易知解法正确性。
二元关系
列举所有二元关系的建图方式。
可建图
对于一般图，以下二元关系同时出现也均可用最大权闭合子图描述。
① b_u=1\land b_v=0 有代价 w
模型上述。
② b_u=1\land b_v=1 有收益 w
建立新点 x，令 a_x=w 并连边 (x,u,\infty),(x,v,\infty)。意义是选 x 则必选 u,v；而 u,v 被选时由于 x 正权，选择 x 一定更优。
③ b_u=0\land b_v=0 有收益 w
建立新点 x，令 a_x=w 并连边 (u,x,\infty),(v,x,\infty)。意义是选 u,v 中的一个则必不选 x；而 u,v 不被选时由于 x 正权，选择 x 一定更优。
注意：同时出现 ②③ 时不认为两条件等价。
试看看：P4313 文理分科
不可建图
对于一般图，以下二元关系出现其一则不可用最大权闭合子图描述。
④ b_u=1\land b_v=1 有代价 w
取 w=+\infty，规约一般图独立集。
⑤ b_u=1\land b_v=0 有收益 w
### 伪不可建图
出现不可建图的模型时，其往往不为一般图而是二分图，此时便可翻转限制解决。
具体做法：将点黑白染色，使任意一条 ④⑤ 限制的两端点不同色。将所有白点权值取反，将所有限制中的白点限制取反，造成的差价初始时累加进贡献。
试看看：[CF311E Biologist](https://www.luogu.com.cn/problem/CF311E)
疑问：若图中既存在可建图二元关系，又存在不可建图二元关系，且不能通过翻转限制解决，那我也不知道怎么办！不知道有没有高明的办法 =.=
### 二元关系（或）
或的二元关系和与的二元关系只是补集转化的关系而已。举个例子：
> $b_u=1\lor b_v=1$ 有代价 $w
这个二元关系不成立，当且仅当 b_u=0\land b_v=0。所以直接给答案累减去 w，就转化为了其补集 ③。
试看看：AT5203 [AGC038F] Two Permutations，但需要一定转化。
多元关系
懒得写了！自己讨论去。