Part 2.5.1 负环

当一张图中有负环时，这张图中经过负环的两点间最短路就不存在。因为可以无限次经过这个负环，使代价不断减小。

在三种最短路算法中，SPFA是唯一一种可以处理负环的算法。

由SPFA的过程，每个点最多会被其他点各更新一次，即入队次数不会超过$n$。

因此如果一个点的入队次数达到了$n+1$，就说明图中存在负环。

SPFA判负环的复杂度是$O(nm)$。

例题2.5.1 [FAIOJ30086]判断负环

模板题。

例题2.5.2 [FAIOJ30085]虫洞

本题判断的就是起点到起点的距离是否小于0。

注意，有负环并不意味着条件成立。例如：

1
3 0 3
1 2 1
2 3 -1
3 2 -1

虽然有负环$(2,3)$，但仍然不能回到$1$。

我们从第一个入队次数大于$n$的点开始搜索，如果这个点可以到达$1$号点，则YES。否则NO。

复杂度$O(nm)$

例题2.5.3 [HNOI2009][FAIOJ20900]最小圈

求无向图最小平均环长。

“最小化平均值”→二分答案。

然后按01分数规划的套路把所有边权都减去答案$x$。

则问题转化为是否存在正环。如果存在，则答案上调；否则答案下调。

所以把所有边权取反，SPFA判负环即可。

复杂度$O(nm\log W)$。

Part 2.5.2 差分约束

给出一些整数变量和一些不等关系：

$x_1,x_2,\dots ,x_n$

$x_i-x_j\le w$

我们把所有的变量看成<stron>，关系看成边。</stron>

把变量的值看成最短路，则有$di{s}_i\le di{s}_j+w$

因此对于每个不等关系都连接一条$i$到$j$的边权为$w$的边即可。

例题2.5.4 [SCOI2011]糖果

这是差分约束的模板题。

如果$di{s}_u==di{s}_v$，可直接用并查集合并这两个点。

如果$di{s}_u\le di{s}_v$就从$v$向$u$连一条$0$的边。

如果$di{s}_u<di{s}_v$，由于糖果的数量全是整数，所以就是$di{s}_u\le di{s}_v-1$，即从$v$向$u$连一条$-1$的边。

如果有负环就输出-1。最后求出所有最短路之和，再加上最短路的最小值加1乘$n$（因为每个数至少为$1$）即可。

复杂度$O(m)$（边权都是$01$所以是线性的）。

例题2.5.5 [FAIOJ30087]Intervals

设$p_i=1$表示第$i$个数被选中，$=0$表示没被选中。

则有${\sum }_{i=l}^r{p}_i\ge c$。

看到区间和就可以想到前缀和优化。所以设$s_i={\sum }_{i=1}^i{p}_i$

则有$s_r-s_{l-1}\ge c$，即$s_{l-1}\le s_r-c$。从$r$向$l-1$连$-c$的边即可。

同时由于$p_i\in 0,1$，故有$s_{i+1}-1\le s_i\le s_{i+1}$。同样连边即可。

于是转化为标准的差分约束模型。求出最短路后答案即为$s_n-s_0$。

复杂度$O(nm)$，随机数据下接近$O(m)$。

例题2.5.6 [FAIOJ30090]layout

首先依题意建图。把$\ge$的关系转化为$\le$再连边。

注意题面中$p_1\le p_2\le \cdots \le p_n$也要连边。

对于两种无解：

如果存在负环，则输出-1；

如果不存在负环且$1$与$n$不连通（即$di{s}_n=inf$），则输出-2。

其他情况输出$di{s}_n$即可。

复杂度$O(nm)$，随机数据下接近$O(m)$。