图论4
1.2-sat
一种优化的方法，定好一个未知数，求另一个未知数
例A && !B=true
A=1,B=0
A=0,B无解
2.图论综合
结合了很多种和图论有关的算法
3.例题
i. 关押罪犯
考虑并查集做法
为每个犯人xi 建一个虚拟节点yi
从大到小处理犯人之间的关系
用 合并xi和yj、xj和yi 来代表 将两个犯人xi,xj分到两个监狱
若两者已在同一个集合，则这对犯人的怨恨值即为最小答案
复杂度O(m)
再考虑使用2-sat建立约束
要将两个犯人分至不同监狱，约束应为
xi && xj == 0
yi && yj == 0
所有约束连边都是双向边
因此可以将 维护有向图强连通分量的tarjan 简化为 维护无向图连通分量的并查集
ii.P2296
仅有一个终点，而不知起点。那么显然任意路径都会将终点作为路径上的一个必然点。利用所有路径的这个通性，改变思路，转而走反向图，就能改为从 已知的起点 , 走到 未知的终点 了。
未知的起点，确定的终点。如果枚举起点跑到终点的话自然不优，所以我们可以将条件转换，从已经确定好的终点反向查找起点，复杂度就会下降很多。
iii.P3275
SPFA：hack数据超时
正解：可以用缩点的方法做。首先只加上1、3、5三种情况的边，如果a<=b那么a向b连边，如果相等就两边都连。然后我们用Tarjan缩一遍环，然后可以构出一个DAG(有向无环图)。由于缩掉的都是1、3、5情况的边，那么他们构成的环就意味着环上的点必须相等。缩环之后重构图，加上2、4情况的边，这个时候要特判：如果此时有一条2、4的边构成自环（意味着它在原图中连接了两个必须相等的点），所以直接输出-1结束。然后我们给图来一遍拓扑排序，如果此时出现环（拓扑排序有些点没有访问到），必然意味着后面新加的2、4情况的边构成了环（1、3、5情况的边已经没有环了），此时也要直接输出-1结束。最后按照拓扑序来一遍dp就可以得出结果。
组员：我、李青宸、陈仲安、徐铭泽、李秉恒