图论基础知识总结

• 列表项

Floyd的最外层循环k的原理

$$f_{ij} = min(f_{ik} + f_{kj})$$
需要保证右侧内部元素是最新的，即由 $k - 1$ 更新后的。
如果将 $k$ 放内层，右侧元素是未被更新的。

例子

当算法跑到 i= 1，j = 2; k = 4;时

k循环在内部：
点1-2的路径只能通过单一的点，要么3（3-2路径还没被优化，所以没有路），要么4（1-4路径还没被优化，所以没有路）来优化路径，没有考虑到同时使用3，4来优化，于本意相反

k循环在最外部：
先用 k = 3优化 使得i->j->k :1->3->4 这样点对1-4就有路径了
k = 4 时 就可以得到 1->4->2; (1->4已经通过3优化了，相当于3也优化了1->2)，所以点对1-2的路径可以被3，4共同优化

spfa算法求负环问题

1. 统计每个点入队的次数，如果某个点入队 $n$ 次，则说明存在负环 。

2. 统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于 $n$ ，则也说明存在负环
   注：

   spfa在众多问题中的广泛应用，较大程度上得益于他的优秀的复杂度 $O(n+m)$ 。但在大多数时候，spfa的复杂度是趋近于 $O(nm)$ 的。
   所以在某些题目中我们可以是用些取巧的玄学做法。
   例如说，在spfa求负环的大多数问题中，当所有点的入队次数超过 $5n$ 时，我们就认为图中有很大可能时存在负环的，当 $n$ 的范围很大时，我们可以使用这种方法，以避免超时。（若不是到逼不得已不要用……）
   还可以将spfa中的队列换成栈 ， 这样可以大大降低复杂度，在有负环的情况下跑的飞快。（别用STL里的栈）（慎用）

某些出题套路及解决方法

1、很多时候，题目中的负环不一定能从起点走到，所以在进行 $spfa$ 的时候我们可以先将所有的节点入队。之后正常跑 $spfa$ 就ok了。
2、$dis$ 数组不需要赋初值

01分数规划问题

01分数规划问题就是求一个类似

$$\frac{\sum_{i = 1}^{k}f_i}{ \sum_{i = 1}^{k}t_i}$$
的极值问题。

咕咕……

---

差分约束问题

差分约束问题就是给你一个不等式组，让你求这个不等式组的一组可行解。

建立模型

首先，可以想到，在求解最短路问题时我们使用的三角不等式。若此时的 $X_i$ 表示起点到 $i$ 点的单源最短路的长度，$j$ 表示 $i$ 的一个入度点，两点之间的边权为 $C_k$ 。

$$X_i <= X_j + C_k$$
这个不等式显然成立，所以我们可以类比此类思想，将求解不等式组转化为图上问题。图中必须有一点从这一点出发可以便利到每一条边，称为源点（若无源点可自建虚拟源点）
举例
1、不等式组无解，则图中必有负环
2、若图中无负环，那么 $dis_i$ 就是原方程的一组可行解

常见问题变形

在差分约束问题中常见一种求解变量最值的题型。这种题型
必会给出至少一个类似 $x_i <= k$ 的方程。
因为，若无此类方程多个不等式组之间的关系都是相对的，此时求出的一组解任意同时加或减不等式仍然成立（不等式的性质），所以如果有一组最小或最大的解时，必须要有类似 $x_i <= k$ 方程来对求出的解进行限制（这类方程是绝对的）。
对于这类方程的连边，我们采用建立虚拟源点的方式，例如 $x_i <= k$ ，可以建立一个 $0$ 边，将方程变成 $x_i <= x_0 + k$ 的形式，即建立一条由 $0$ 点至 $x_i$ 边权为 $k$ 的边 。
结论：
1、求某点最大值跑最短路
2、求某点最小值跑最长路
证明：
以求解最大值为例，在求解最短路时我们需要将每个不等式转化成 $x_i <= x_j + c_k$ 的形式这里我们建的每一条边 $j\frac{c_k}{}$>$i$ ,因为在建边的时候我们是类比最短路三角不等式的未松弛之前的状态，所以说图上每条边的距离都是在满足不等式的情况下理论上最长的。在跑最短路的过程中，我们每一次松弛操作更新出的 $dis_i$ 都是 $x_i$ 的一个可行解，但在跑完最短路后的 $dis_i$ 一定是 $x_i$ 的一组最小可行解。结合上述建图的含义，这里的 $dis_i$ 就是 $x_i$ 的一个最小的最大值。也就是 $x_i$ 的最大值。
为什么要找最小的最大值呢？我们这里同样结合连边建图的含义，现在将 $dis$数组 从图上的转化到不等式层面来，跑最短路过程中的每一个时间点的 $dis_i=k$ 都代表了一个不等式组 $x_i <= k$ 我们找出一个满足所有的不等式的解，即 $k$ 的最小值。跑完最短路后的 $dis_i$ 就是最小的 $k$ 。
最小值同理。
简单的记忆方法
1、在求解最短路时我们需要将不等式转化为类似

$$X_i <= X_j + C_k$$
的形式，我们不等式中只会出现 $<=$ 符号。解，小于等于的一定是最大值（解，一定小于等于最大值）
所以求解最大值问题时就跑最短路
2、在求解最长路时我们需要将不等式转化为类似
$$X_i >= X_j + C_k$$
的形式，我们不等式中只会出现 $>=$ 符号。解，大于等于的一定是最小值（解，一定大于等于最小值）
所以求解最小值时就跑最长路。

2—sat问题

sat问题是适应性问题的简称，一般有单sat问题，2-sat问题，和k-sat问题三种 $(k > 2)$ ，其中 $k-sat$ 问题是 $NP$ 完全的 ，好像还是21世纪几个未解数学难题之一。所以这里我们讨论 $2-sat$ 问题 。$2-sat$ 给出几个变量和关系表达式（每个表达式只会有2个变量），每个变量只有两种状态 $真或假$ ， 求解满足要求的一组解 。

整体做法，

基本公式 $¬a→b∧¬b→a$

1、第一步，如下图所示

图片来自@Anguei的博客，如有侵权请联系删除
2、第二步，考虑多解成立的情况
采用数学方法“带入解看方程是否成立”

截图来自@暗ざ之殇的博客，如有侵权请联系删除
（我只是懒~而且人家讲的已经很好了~）
连着写了三道 $2-sat$ ，感觉这种题有很明显的特征，你可以很容易的看出来。但是我们还要仔细分析题目找出一种具有传递性的关系。用连边的方式表示该关系。这个关系还要能够较简单的判断出答案。

所以针对2-sat问题，最重要的是分析！设计出点联通的意义