2-sat&&网络流建图技巧

Skadi_H · 2024-08-04 22:06:31 · 算法·理论

前言

很多时候，对于一个问题，我们可以运用一些技巧，运用图论当中算法的优秀性质或表示含义，进行图论建模，将一个其他妖魔鬼怪的问题转化为图论问题，在这里我们主要探讨省选组别当中的2-SAT和网络流建图技巧。

2-SAT

简介

2-sat常常被用于多组数据或者询问结合起来的二选一问题。

实际上，常见的维护“二选一”操作的有两种算法：

一个就是2-sat，它用于对每一项进行二选一。

另一个就是最小割，它更倾向于将一个集合划分为A,B两部分。

在此文章中，我们默认读者能够轻松写出2-sat的板子，只讨论一些套路的建图技巧。

序列

problem 1

quest

使用 O(n) 条边，表示限制：

很显然，我们要维护以下关系：

但2-sat并不能维护三元关系的式子，所以我们考虑下面一组与其类似的关系：

很显然它能够成功的表示所有必须 y_i=1 的情况。

但是，当 x_i=y_{i-1}=0 时，y_i=0/1 均是合法的。

但这并不会影响我们的算法，因为此时我们取 y_i=1 的时候一定严格不优于取 y_i=0 的时候。

于是我们就成功用 O(n) 条边完成了这个题目

但是因为一些神奇的原因，可能是实现上的因素，导致我需要对正反都连一次边才能保证正确性。

problem 2

quest

使用 O(n+qlogn) 条边，表示限制：

给出 q 个区间 [l,r]，构造一组方案使得对于所有满足对于所有区间，只能至多出现 1 个 1 。

ans

对 [1,n] 建线段树，并对每个节点 idx 建一个辅助变量 y_{idx}：

• 对于表示 [i,i] 的叶子结点 idx ：x_i=1 \rightarrow y_{idx}=1

• y_{lson}=1 \rightarrow y_{idx}=1
• y_{rson}=1 \rightarrow y_{idx}=1

对于所有被限制的区间 [l,r] 对应的结点：

• y_{idx.lson}=1 \rightarrow y_{idx.rson}=0
• y_{idx.rson}=1 \rightarrow y_{idx.lson}=0

对于每一个限制 [l_i,r_i]：

假设其在线段树上被分成了若干个区间 idx_1,idx_2,...,idx_k

我们开辅助变量 z_1,z_2,...,z_k

其中 z_i=y_1 or y_2 or...or y_i

• y_{idx_p}=1 \rightarrow z_p=1
• z_{p-1}=1 \rightarrow z_p=1
• z_p=1 \rightarrow z_{p+1}=0

然后就没了

边数：O(qlogn+n)

problem 3

quest

使用 O(n) 条边，表示以下限制：

给定一棵 n 个节点的有根树，如果 u 是 v 的祖先，那么 x_u 与 x_v 不同时为 1

ans

这个条件可以转化为：

• 在 x_u=1 \rightarrow x_v=0,(v \in subtree_u)

令 y_u=OR_{v \in subtree_u} x_v

所以条件就变为了：x_u 和 所有y_{child_u} 当中至多出现 1 个 1

于是我们可以建辅助变量，z_v,(v \in subtree_u)

满足条件 y_v and x_u=0

所以我们对每一组约束条件，建出：

problem 4

quest

使用 O(nlogn) 条边，表示以下限制：

• 每个 bool 变量 x_i 关联一个区间 [l_i,r_i]

• 若 x_i,x_j 同时为 1 则必须 [l_i,r_i],[l_j,r_j] 不相交

ans

设区间 [l,r] 所对应的结点为 idx_1,idx_2,...,idx_k，对应区间为 [a_1,b_1],...,[a_k,b_k] 。

在某个给定的区间 [l_i,r_i] ，将 x_i 挂在 idx_{i_1},idx_{i_2},...,idx_{i_k} 上。

很显然，所有的 idx_{i_1},idx_{i_2},...,idx_{i_k} 只能选一个。

而若 idx_{i_p} 被选了，那么 idx_{i_p} 的所有祖先节点都不能选。

基于这样的考虑，我们可以建图：

同样还是对线段树上的每个节点开一个辅助变量 y_i

对于区间 [l_i,r_i] ，将 x_i 挂在所有的结点 idx_1,idx_2,...,idx_k 上

• 假设节点 idx 上挂了一些点 x_{i_1},x_{i_2},...,x_{i_m}：

  • 开辅助变量 z_{i_0},z_{i_1},..,z_{i_k}

  • x_{i_p}=1 \rightarrow z_{i_p}=1
  • z_{i_{p-1}}=1 \rightarrow z_{i_p}=1
  • z_{i_p}=1 \rightarrow x_{i_{p+1}}=0
• z_{i_p}=1 \rightarrow y_{i}=1
• z_{idx.lson}=1 \rightarrow z_{i_0}=1
• z_{idx.rson}=1 \rightarrow z_{i_0}=1

网络流

网络流的建图无非就是两种思路：

• 流建图，流量表示选择（数量多少）

• 割建图，运用最大流最小割定理，流量表示去除该条的贡献。

接下来，我会分别对这两部分建图的一些技巧进行一些整理。

流建图

由于现在时间比较紧迫，我只整理一些要点&&技巧。

1.超级源点 SS 向 S 连一条流量为 f 的边，表示限制某东西最多选择 f 个/次，一般配合最大流食用。

2.将一个点 i 拆成 in_i，out_i 两个点，若流过 in_i\rightarrow out_i 表示选择了 i 这个点。

3.差分建图，例如维护 val^2 类型的贡献满足对于 i<i+1 时 val_i-val_{i-1}<val_{i+1}-val_i(即变化量随下标增大而增大) 的一类东西，可以通过建多条 流量为 1 ，费用为 2*i-1 的边，使得其能 通过 最小费用最大流 贪心的凑出 i^2

后面我想到什么再往上补充吧。

割建图

1.最大闭合子图问题，相当经典，是 2-SAT 以外的另一个二元集合划分的考虑方向。

2.（1）中有一个很好的思想，可以在其他地方进行考虑：如果强制选择A就必须选择B，可以连一条 (A,B,inf)的边跑最小割，它就一定不会被割掉。

3.割建图同样可以表示选择，对于 n 个选项，可以建 n+1 个点连成一条链，在哪里 (i,i+1) 处断开，就表示选择 第 i 个选项。

等我想到再补充吧