最短路应用

差分约束

定义

一组形如约束条件形如 $x_a - x_b \le c$ 找出一组解，使得所有约束条件都成立。

解法

最短路三角形不等式

设 $dist[v]$ 是从源点到 $v$ 的最短距离，那么对于任意一条边 $u \rightarrow v$ 权值为 $w$，必有： $dist[v] \le dist[u] + w$ 移项得到： $dist[v] - dist[u] \le w$

这恰好就是 $x_v - x_u \le w$ 的形式

建图

• 对不等式 $x_v - x_u \le c$，连一条从 $u$ 到 $v$、权值为 $c$ 的有向边。
• 求最短路径值 $dist$，可作为不等式的一组解。

注意以下两点

• 如果有负环，说明约束条件矛盾，无解
• 如果图不连通，需要添加超级源点

传递闭包

定义

全局可达性问题，对于 $n$ 个节点的图，传递闭包是一个 $n \times n$ 的矩阵 $R$，$R_{uv}$ 表示从点 $u$ 是否能到达点 $v$。

解法

把边权转换为“可达性”的布尔值，求全源最短路

• 有边设 1，无边设 0
• 使用 Floyd 算法求全源最短路

vector<vector<bool>> R;
for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            R[i][j] |= (R[i][k] & R[k][j]);

优化

使用 bitset 优化，复杂度降为 $O(n^3 / 64)$

vector<bitset<MAXN>> R;
for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
        if(R[i][k]) R[i] |= R[k];