2023.7.21

[邵品砚]

2-sat

应用：

• 解决布尔可满足问题。即有多个布尔变量，每个的取值可能为true/false 有多个形如↓的公式

(not) x and / or / xor (not) y = true / false

思路：

• 避免题目条件的浪费，观察每条公式中对变量的限制

• 将x，y分成x0，x1，y0，y1，对于每条公式根据其限制关系连边

• 若存在一个元素x，从x0可以走向x1，从x1可以走向x0，则无解；若x0和x1在同一个强连通分量内，则无解

• 因此对建出的有向图跑tarjan求强连通分量，检查每个变量的两个点是否在同一个强连通分量内即可判断无解

• 输出时对每个元素选强连通分量编号较小(逆拓扑序较小/拓扑序较大)的作为取值

例题

eg1: 关押罪犯

思路：

• 考虑并查集做法，为每个犯人xi建立一个虚拟节点yi

• 按怨恨值从大到小处理犯人之间的关系(贪心)

• 合并集合来代表将犯人分到两个监狱，若两人已经在同一个监狱，则两人的怨恨值即为最小答案

• 而并查集的解题思路就来源于2-sat

• 考虑用2-sat建立约束，即

x xor y == 1

• 由于所有约束连边都是双向边(xor符合交换律)，因此可以将维护有向图强连通分量的tarjan简化为维护无向图连通分量的并查集

eg2: 游戏

思路：

• 考虑不存在x的情况，就可以直接用2-sat建图解决

• 注意到x的数据范围很小，只有8，考虑暴力枚举使用哪些车辆，但复杂度过大，舍去

• 我们可以枚举这8张地图不使用哪些车辆，再跑2-sat

eg3: 糖果

思路：

• (一眼丁真） 差分约束，将题目转化后建边,然后跑最长路

• 考虑到每个小朋友都有糖果的情况，建立一个超级源点s代表分得糖果数为0，对所有小朋友有xi-s>=1

• 由于spfa被卡死，考虑跑tarjan；发现条件1、3、5建出的边的权值都为0，再对所有强连通分量缩点

---

建模

eg4: 求最短路的最小值

思路：

• 1.Dijkstra把s个点全设为0，都丢入优先队列

• 2.建立超级起点，超级终点，将小起点，小终点分别与超级起点，超级终点连一条权值为0的边

eg5: 求两两最短路的最小值

思路：

• 想办法转化为eg4，对其进行二进制分组，即枚举二进制位

• 将s个数按枚举的位是0还是1分为两组，一组起点，一组终点，答案对所有分组的最短路取min

• 由于答案的起点和终点的编号不同，一定会在某次分组中被分到两组

eg6: 前缀连边求最短路

思路：

• 建立虚点 u1, u2, u3……每个ui向原图的节点i连一条长度为0的有向边。如果 i > 1,ui 向 ui - 1 连一条边，可以将边数优化为(n + m)条

eg7: 区间连边求最短路

思路： 线段树优化建图

eg8: 两两连边求最短路

思路：

• 对每组边建立一个新点，组内所有点与新点连边，边权为v/2，跑最短路即可

eg9：汤圆防漏理论

思路：

• 贪心：每次取出相邻的边的边权之和最小的点夹出

• 二分硬度的上界，使用类拓扑的做法，将低于二分上界的点删除，并修改点权，，判断能否将所有点删除即可

eg10: BIU-Offices

• 题意要求一个图最少可以划分成几个团，在转化为求补图的连通块个数，但边数为(n^2)

• (不考，不写，不学) 链表优化bfs，利用链表的O(1)删除优化,复杂度O(n+m)

eg11: 寻找道路

思路：

• 从终点反跑dfs，标记所有跑到的点，删去所有无标记的点和指向无标记的点，再跑Dijkstra

eg11: Milk Kountain

思路：

• 从终点反跑dfs，标记所有跑到的点，删去所有无标记的点和指向无标记的点，再跑Dijkstra

• ###双倍经验：Milk Pumping G
  小组成员:邵品渊， 邵品砚， 蒋佳成， 顾天泽， 马天翔， 陈继禹