NOIP GRAPH

1. 可持久化并查集

直接用可持久化线段树维护可持久化数组

2. 基环树

一种出题人经常拿来强行增大题目难度的工具。

可以通过断边或者分讨的方式处理。

3. 2-SAT

2-SAT 使用拆点表示 bool 取值，用有向边代表变量之间推导的关系。

图中强连通分量就代表了一套等于关系，里面所有变量取值都相等，对应里面所有包含的点所代表的赋值方式都同时成立或者不成立。这样，我们缩点之后用逆 Topo 序。

P6378 Riddle

每个点有选和不选两种选择，题目给出的限制信息就是一种推出其他状态的方式，可以用 2-SAT 建模。但是我们发现我们需要给集合其他部分连边，这样就太多了，我们有一种优化：

Trick 前缀和优化：做一个前后缀和，直接朝上面连。

P3825 游戏

这个是笔者刚刚胡的

观察到原题目等价于有很少点是 3-SAT 的 2-SAT。这种点非常少，可以考虑暴力枚举所有这种点不能取哪一个，然后跑 2-SAT \(\mathcal O(3^d(n+m)) = 6.5\times 10^8\)

与之相近的，还有差分约束，是借助 \(x_i\le x_j+\mathbf{edge}(j\to i)\) 来计算一系列不等式组的方法。其实跑最短路算法的过程，就是不断地进行松弛使得所有边都满足上述条件的过程（除非有负环，否则肯定可以全部满足）。

4.网络流

重点不在于打板子，反正又不可能卡 Dinic。 重点在于建图。

P2766 最长不下降子序列问题

建图，我们要秉持一种算贡献的思路，就是一点流量要流到终点成功贡献出去的话，就必须借助一些桥梁，就是要满足一些限制条件。所以对于统计方案的题目，我们建图的思路也应该是一点流量通过的路径就应该是一种合法方案。

先考虑我们应该把每一个元素作为桥梁，表达只能选择一个，可以用常见技巧：拆点

以下，设序列的最长不下降子序列长度 \(len=\max_{i=l}^r{f_i}\)

所以，以第二问为例：令 \(f_i\) 为以 \(i\) 结尾的最长不下降子序列长度，如果：

• \(f_i\) 满足 \(f_i=len\) ，那么，这个点是一个合法方案的终点，应该连边 \(\mathbf{out}(i)\to \bf T\)

• \(f_i\) 满足 \(f_i=1\) ，那么，这个点是起点，应该有 \(\mathbf{S}\to \mathbf{in}(i)\)

• 如果 \(a_i\le a_j,i<j,f_i+1=f_j\) ，那么，从 \(i\) 就可以一步转移到 \(j\) ，连边 \(\mathbf{out}(i)\to \mathbf{in}(j)\)

UVA1660 电视网络

点连通度可以通过拆点转化成求最小割。

所以，怎么求最小割？？？

Theorem 最大流最小割定理

一个网络的最大流等于最小割。

这个结论可以通过跑网络流算法的过程来理解。因为一条增广路的流量其实是由最小流量边限制的，当跑完之后最小流量的边就全部满流了，相当于全部被割掉了，当全部增广路都没有的时候，说明 \(S\) 和 \(T\) 已经被分成两部分了。

P2598 狼和羊的故事

就是要把原图上两个颜色块分开，所以考虑用最小割，把狼全连到 \(T\) ，羊全连到 \(S\)，狼羊直接交互的地方边权为 1，其余部分为 \(+\infty\)

P1251 餐巾计划问题 [!]

遇到这种限制，我们可以用最大流的最大性进行满足。

那么，在网络中流动的东西，也就是餐巾，他其实是有状态的，要么是干净的要么是脏的，然而”脏的“流，我们是不允许他产生贡献的，他必须通过快洗或慢洗转换成干净的流，然后才能贡献。

我们为了分别满足每一天的要求，每一天都要收集贡献，但是每一天可能同时存在干净的流和脏的流，但是我们是没办法在流上打标记的，所以为了区分，我们把每一天的餐巾存储库拆成干净存储库和脏餐巾存储库，我们有以下连边：

• 从 S 向 每一天的干净餐巾存储库连 INF,p 的边，表示可以购买来填充干净餐巾存储库

• 从 每一天的干净餐巾存储 向 T 连 \(r_i\) ,0 的边，表示使用了这些餐巾

• 从 S 向 脏餐巾存储连 \(r_i,0\) 的边，表示今天产生了 \(r_i\) 脏餐巾（前面的已经贡献给 T 了）

• 从 脏餐巾存储向 m 天之后的干净餐巾存储连 INF,f 表示快洗

• 从 脏餐巾存储向 n 天之后的干净餐巾存储连 INF,s 表示慢洗

• 从 脏餐巾存储 向 明天的脏餐巾存储连 INF,0 表示不洗

显然根据最大流的最大性，每一天会且仅会产生 \(r_i\) 脏餐巾，上面的方法显然正确。