Day07
2-SAT
SAT是适定性(Satisfiability)问题的简称。一般形式为k-适定性问题简称 k-SAT。可以证明，当k>2时，k-SAT是NP完全的.因此一般讨论的是k=2的情况，即2-SAT问题
适定性问题
数学术语适定性问题来自于哈达玛所给出的定义。他认为物理现象中的数学模型应该具备下述性质：
- 存在着解
- 解是惟一的
- 解连续地取决于初边值条件
适定性问题的原型范例包括对于拉普拉斯方程的狄利克雷问题，以及给定初始条件的热传导方程式。在物理过程中解决的这些问题，也许被视为“自然”问题。相较之下，反向热导方程，推演来自最终数据的温度的稍早分布就不是适定的，因为这个解对最终数据极为敏感。一个问题如果不是适定的，哈达玛就将其视为不适定。逆问题通常是不适定的。这些连续问题必须使其离散，以取得数值解。泛函分析问题通常是连续的，当以有限精度或存有错误的资料求解时，它可以承受这些数值的不稳定性。即使一个问题是适定的，它也可能仍是病态的；即在初始资料中的一个微小错误，可以造成很大错误的答案。病态问题以大的条件数表示。如果某一个问题是适定的，它就有机会在使用了稳定算法的电脑上取得解。如果问题是不适定的，就需要为数值处理重新以公式表示。
2-SAT问题
给定n个变量ai，每个变量能且只能取0/1的值，同时给出若干条件，而求解2-SAT的解就是求出满足所有限制的一组a。
实际意义
比如邀请人来吃喜酒，夫妻二人必须去一个，然而某些人之间有矛盾（比如 A 先生与 B 女士有矛盾，C 女士不想和 D 先生在一起），那么我们要确定能否避免来人之间没有矛盾，有时需要方案。
解决方法
首先我们考虑将2-SAT问题往图论的方向靠，我们发现每个点要么取 0 ，要么取 1 。因此对于 ai ，我们建两个点 2i−1 与 2i 分别表示 ai 取 0 和 1 然后我们考虑建边来表示这些关系，我们令一条有向边的意义：x→y 表示如果选择了 x 就必须选 y 。
那么我们可以举一些简单的例子来总结下连边的规律（用i′表示i的反面）：
i,j 不能同时选：选了i就要选 j′ ，选j就要选 i′ 。故 i→j′,j→i′ 。一般操作即为ai xor aj=1。
i,j必须同时选：选了i就要选j，选j就要选i。故i→j,j→i。一般操作即为 ai xor aj = 0 。
i,j任选（但至少选一个）选一个：选了i就要选j′，选j就要选i′，选i′就要选j，选j′就要选i。故i→j′,j→i′,i′→j,j′→i。一般操作即为ai or aj = 1 。
i必须选：直接i′→i，可以保证无论怎样都选i。一般操作为给出的 ai = 1 或 ai and aj = 1
建好图然后就是考虑怎么用图论的方式解决 2-SAT 了。
Tarjan SCC 缩点
前导知识：
在有向图中，如果两个顶点至少存在一条路径（可以相互通达），则称两个顶点强连通。
如果有向图G的每两个顶点都强连通，称G是一个强连通图。
非强连通有向图的极大强连通子图，称为强连通分量。
Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。
Tarjan 算法求强连通分量
在 Tarjan 算法中为每个结点 u 维护了以下几个变量：
dfn[n] ：深度优先搜索遍历时结点 u 被搜索的次序。
low[u] ：设以 u 为根的子树为 Subtree(u) 。low[u] 定义为以下结点的 dfn 的最小值： Subtree(u) 中的结点；从 Subtree(u) 通过一条不在搜索树上的边能到达的结点。
一个结点的子树内结点的 dfn 都大于该结点的 dfn。
从根开始的一条路径上的 dfn 严格递增，low 严格非降。
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中，对于结点 和与其相邻的结点 v （v 不是 u 的父节点）考虑 3 种情况：
- v 未被访问：继续对 v 进行深度搜索。在回溯过程中，用 low[v] 更新 low[u] 。因为存在从 u 到 v 的直接路径，所以 v 能够回溯到的已经在栈中的结点，u 也一定能够回溯到。
- v 被访问过，已经在栈中：即已经被访问过，根据 low 值的定义（能够回溯到的最早的已经在栈中的结点），则用 dfn[v] 更新 low[u] 。
- v 被访问过，已不在在栈中：说明 v 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 dfn[u]=low[u] 。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 DFN 值和 LOW 值最小，不会被该连通分量中的其他结点所影响。
因此，在回溯的过程中，判定 dfn[u]=low[u] 的条件是否成立，如果成立，则栈中从 u 后面的结点构成一个 SCC。
{ 1，2，3，4}，{ 5}，{ 6} 为三个强连通分量。
struct ss{
int v;
int next;
}s[1000];
int head[1000];
int dfn[1000];
int low[1000];
int vis[1000];
int color[1000];
int cnt;
stack<int >st;
void Tarjan(int u) {
st.push(u);
dfn[u] = low[u] = ++cnt;
vis[u]=1;
for(int i = head[u]; i != -1; i = s[i].next) {
int v = s[i].v;
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(vis[v]) {
low[u] = min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]) {
int now;
do {
now=st.top();
color[now]=u;
vis[now]=0;
st.pop();
}while(now!=u);
}
return;
}我们举个例子来讲：
假设有 a1 , a2 和 b1 , b2 两对,已知 a1 和 b2 间有矛盾，于是为了方案自洽，由于两者中必须选一个，所以我们就要拉两条有向边( a1 , b1 )和( a2 , b2 )表示选了 a1 则必须选 b1 ，选了 a2 则必须选 b2 才能够自洽。
然后通过这样子建边我们跑一遍 Tarjan SCC 判断是否有一个集合中的两个元素在同一个 SCC 中，若有则输出不可能，否则输出方案。构造方案只需要把几个不矛盾的 SCC 拼起来就好了。
输出方案时可以通过变量在图中的拓扑序确定该变量的取值。如果变量 !x 的拓扑序在 x 之后，那么取x值为真。应用到 Tarjan 算法的缩点，即 x 所在 SCC 编号在 !x 之前时，取 x 为真。因为 Tarjan 算法求强连通分量时使用了栈，所以 Tarjan 求得的 SCC 编号相当于反拓扑序。
时间复杂度为O（n+m）。
例题 HDU3062 Party
题面：有 n 对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有 1 人可以列席。在 2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的 2 个人是不会同时出现在聚会上的。有没有可能会有 n 个人同时列席？
练习
最小生成树
- 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
- 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
Kruskal算法（加边法）
- 将图中所有边按边的权值从小到大进行排序。
- 将 n 个顶点看作 n 棵树。
- 选择值最小的一条边，如果两个端点未在一颗树上，就把该边作为最小生成树的一条边，合并两棵树。
- 重复 3 ，直到加入 n-1 条边。
Prim算法（加点法）
- V 为目的点集，U 为初始点集，另 W = U - V。初始化 V = { s }。
- 在 V 和 W 两个集合能组成的边中，找出权值最小的边（ v0 , w0），把 w0 加入到 V 中。
- 重复 2 ，直到 V 中包含所有点。
习题
最大流
我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。
网络流简介
首先，请分清楚 网络 （或者流网络，Flow Network）与 网络流 （Flow）的概念。
网络是指一个有向图 G = (V ,E) 。每条边 (u,v) 都有一个权值 c(u,v) ,称之为容量。其中有两个特殊的点：源点和汇点 。
设 f(u,v) 定义在二元组 (u,v) 上的实数函数且满足
- 容量限制：对于每条边，流经该边的流量不得超过该边的容量。
- 斜对称性：每条边的流量与其相反边的流量之和为 0。
- 流守恒性：从源点流出的流量等于汇点流入的流量。
那么 f 称为网络 G 的流函数，f（u,v） 称为边的 流量 ， c(u,v) - v(u,v) 称为边的 (u,v) 剩余容量 。整个网络的流量从源点发出的所有流量之和 。
残量网络
假定有一个流网络G=（V，E），其源点为s，汇点为t，f为G中的一个流。对即诶点对u，v，定义残存容量
。有：
残存网络可能包含图G中不存在的边，残存网络中的反向边允许算法将已经发送出来的流量发送回去。
一个残存网络示例图如下：
图a是一个流网络，b是a对应的残存网络，注意每条边上的值，残存网络中针对每条正向边计算出该条边在存在流的情况下的剩余容量，并画出一条反向边，反向边的容量即是发出流的大小，方便将发出的流运输回发送地，并将权重为0的边省略。
增广路
在原图 G 中若一条从源点到汇点的路径上所有边的 剩余容量都大于 0 ，这条路被称为增广路。
或者说，在残存网络 Gf 中，一条从源点到汇点的路径被称为增广路。如图：
我们从 4 到 3 ，肯定可以先从流量为 20 的这条边先走。那么这条边就被走掉了，不能再选，总的流量为 20（现在）。然后我们可以这样选择：
- 4 -> 2 -> 3 这条增广路 的总流量为 20 。到 2 的时候还是 30 ，到 3 了就只有 20 了。
- 4 -> 2 -> 1 -> 3 这样子我们就很好的保留了 30 的流量。
所以我们这张图的最大流就应该是 20 + 30 = 50 。
Edmond-Karp 动能算法（EK 算法）
结合上面例子理解，s = 4， t = 3。
#define maxn 250
#define INF 0x3f3f3f3f
struct Edge {
int from, to, cap, flow;
Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct EK {
int n, m; // n：点数，m：边数
vector<Edge> edges; // edges：所有边的集合
vector<int> G[maxn]; // *** x -> x 的所有边在 edges 中的下标
int a[maxn], p[maxn]; // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
// p：点 x -> BFS 过程中最近接近点 x 的边
void init(int n) {
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
int Maxflow(int s, int t) {
int flow = 0;
for (;;) {//每次循环找到一条增广路
memset(a, 0, sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = INF;
while (!Q.empty()) {//bfs寻找增广路
int x = Q.front();
Q.pop();
for (int i = 0; i < G[x].size(); i++) { // 遍历以 x 作为起点的边
Edge& e = edges[G[x][i]];
if (!a[e.to] && e.cap > e.flow) {
p[e.to] = G[x][i]; // G[x][i] 是最近接近点 e.to 的边
a[e.to] =
min(a[x], e.cap - e.flow); // 最近接近点 e.to 的边赋给它的流
Q.push(e.to);
}
}
if (a[t]) break; // 如果汇点接受到了流，就退出 BFS
}
if (!a[t])
break; // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
for (int u = t; u != s;
u = edges[p[u]].from) { // 通过 u 追寻 BFS 过程中 s -> t 的路径
edges[p[u]].flow += a[t]; // 增加路径上边的 flow 值
edges[p[u] ^ 1].flow -= a[t]; // 减小反向路径的 flow 值
}
flow += a[t];
}
return flow;
}
};习题
参考文章
tarjan求强连通分量
tarjan求强连通分量模板
OI Wiki 2-SAT
OI Wiki 最小生成树
最小生成树
OI Wiki 网络流
最大流
