最短路 例题

Center (Easy)

给定一个城市的交通网络（一张带正边权的无向图），每个节点是一个咖啡厅。选择一个节点或者是一条边上的某处建一个餐馆，使得餐馆到最远的咖啡厅的距离最近。输出距离。

$n \le 200$，$m \le \frac {n (n-1)} 2$，无重边和自环。

首先这个数据范围先 Floyd 一下肯定是不亏的。

枚举每条边 $u \leftrightarrow v$，边权为 $w$。设我们把餐馆开在离 $u$ 距离为 $x$ 的地方。一个点 $k$ 到餐馆的距离为

每个点 $k$ 只会发生一次切换，枚举每个切换点用数据结构维护即可。

总时间复杂度 $O(n^3 \log n)$。

优化建图

用一个例题解释我们要干嘛。

💡CF786B Legacy

有一张 $n$ 个点的图，初始没有边。有三种加边操作：

• $u \to v$，权值为 $w$。
• $u \to i, i \in [l,r]$，每条边权值相等为 $w$。
• $i \to v, i \in [l,r]$，每条边权值相等为 $w$。

加完所有的边后跑一个 Dijkstra 单源最短路。

$n,m \le 10^5$。

显然直接连怎么都不对，边数直接就是平方级别。

精妙的构造：按节点编号建立线段树，每个线段树节点对两个儿子连 $0$ 边，叶子对原节点连 $0$ 边。对 $[l,r]$ 内的点连边只要连 $O(\log n)$ 个线段树节点即可。

又有出又有入，开两棵线段树即可。

时间复杂度 2log。

优化建图 例题

BZOJ4699 树上的最短路 (Hard)

洛谷双倍经验：P5344 【XR-1】逛森林

给定一棵无向带正边权树。

有 $m$ 个修改，每一个修改有参数 $l_1, r_1, l_2, r_2, c$，含义是 $l_1 \leftrightsquigarrow r_1$ 上的每一点都向 $l_2 \leftrightsquigarrow r_2$ 上的每一点连了一条边权为 $c$（$c > 0$）的有向边。

给定一个目标点 $k$，求最终图上每个点到 $k$ 的最短路。

$n \le 2.5 \times 10^5$，$m \le 10^5$。

以 $k$ 为终点的最短路，显然转化为反图上 $k$ 的单源最短路径。

3log 做法

路径问题考虑重链剖分 1log。对于重链上的段线段树优化连边 1log。

说一下怎么连边。对于每个修改建一个虚点，从 $l_1,r_1$ 那里连到虚点，再从虚点连到 $l_2,r_2$。

点数 $O(n)$，边数 $O(m \log^2 n)$，Dijkstra 最短路 $O(m \log^3 n)$。

总时间复杂度 $O(m \log^3 n)$，过不了。

2log 做法

Dijkstra 1log 省不了，考虑不用重链剖分和线段树。

考虑一下重剖和线段树的本质是什么：把一条链 / 一个区间分解成若干条不相交的链 / 区间。

在这个情境下，不相交这个性质显然是多余的。可相交区间可以用什么来刻画？ST 表。

树上的 ST 表可以用倍增来实现。总体来说，我们把 $u \leftrightsquigarrow v$ 分解为 $u \leftrightsquigarrow \text{LCA}(u, v)$ 和 $v \leftrightsquigarrow \text{LCA}(u, v)$ 两条祖先后代路径。对于每条祖先后代路径，我们把前 $2^k$ 个点和后 $2^k$ 个点这两个区间连出去（$2^{k+1} \le len$）

这样，我们的修改连边个数就是 $O(m)$ 的了。别忘了建 ST 表有 $O(n \log n)$ 条边。

点数 $O(n \log n)$，边数 $O(n \log n + m)$。令 $n,m$ 同阶，Dijkstra $O(n \log^2 n)$。

总时间复杂度 $O(n \log^2 n)$（令 $n,m$ 同阶）。卡常能过。

1log 做法

分析 Dijkstra 的性质。注意到，Dijkstra 每次都会贪心地选择当前的最优解，也就是说 $l_2 \leftrightsquigarrow r_2$ 一旦被某个虚点更新过就再也不会变了。这个性质就很均摊了！用树上序列并查集来维护。

与此同时，我们要快速找到经过某个点 $x$ 的所有路径。有两种可能性：

• $x = \text{LCA}(u,v)$，暴力。
• $u,v$ 恰有一个在 $x$ 的子树内。线段树按 DFS 序维护一下。
  • 令 $x$ 子树的 $dfn$ 区间为 $[l,r]$。设 $dfn_u < dfn_v$。
  • 我们只要不断查询满足 $dfn_u \in [l,r]$ 的 $dfn_v$ 最大的修改，以及满足 $dfn_v \in [l,r]$ 的 $dfn_u$ 最小的修改。

令 $n,m$ 同阶，总时间复杂度 $O(n \log n)$。

差分约束

是一种形式极为特殊的线性规划问题。

形如 $x_v - x_u \le w$ 的约束，移项 $x_v \le x_u + w$，发现形式很像最短路的三角不等式。在图上用一条边 $u \to v$ 权值为 $w$ 的边表示，跑最短路即为一组可行解。若存在负环说明无解。

非负权图跑 Dijkstra；否则跑 SPFA 时间复杂度 $O(nm)$，但是特殊性质图可能有奇效。

如果是 $x_v - x_u \ge w$ 的约束，可以看作最长路的三角不等式，跑最长路获得一组可行解。

但是注意到这两种约束是可以互相转化的，所以我们做题时需要好好思考应该选择最短路还是最长路的模型。

最短路 or 最长路？

最小可行解对应最长路，最大可行解对应最短路。

具体来说，令 $dis_0 = W$，其中 $0$ 是超级源点，向其它所有点连了一条权值为 $0$ 的边。

• 跑最短路，则所有未知数在 $\le W$ 的前提下达到最大值；
  • 要使用 $x_v - x_u \le w$ 的约束。
• 跑最长路，则所有未知数在 $\ge W$ 的前提下达到最小值。
  • 要使用 $x_v - x_u \ge w$ 的约束。

Ref:

• 差分约束系统
• 图论 I - Alex_Wei

差分约束 例题

UVA1723 Intervals

经典模板题！要熟记本题 Dijkstra 做法。

• 卡 SPFA 的版本：[ABC216G] 01Sequence
• 比较新的版本：P11453 [USACO24DEC] Deforestation S，就是这个题把我从 USACO S 送上了 G（乐）。

[ABC216G] 01Sequence

有一个长为 $n$ 的 $\texttt{01}$ 序列 $a$，但是你不知道具体的每个位置的值。

有 $m$ 个约束，每个约束给定参数 $l,r,x$，要求 $[l,r]$ 内 $\texttt{1}$ 的个数要 $\ge x$ 个。$1 \le x \le r - l + 1$。

输出 $\texttt{1}$ 最少的一种方案，有 SPJ。

$n,m \le 2 \times 10^5$。

$O(nm)$ 做法

建出 $a$ 前缀和 $s_{[0,n]}$。

• $0 \le s_i - s_{i-1} \le 1$，拆成以下两个：
  • $s_i - s_{i-1} \ge 0$
  • $s_{i-1} - s_i \ge -1$
• $s_r - s_{l-1} \ge x$

要求最小可行解，跑 SPFA 最长路。

$O(m \log m)$ 做法

先对 $a$ 所有元素取反，建出 $\lnot a$ 前缀和 $s_{[0,n]}$。

• $0 \le s_i - s_{i-1} \le 1$，拆成以下两个：
  • $s_{i-1} - s_i \le 0$
  • $s_i - s_{i-1} \le 1$
• $s_r - s_{l-1} \le r - l + 1 - x$

要求最大可行解，跑 Dijkstra 最短路。

YamanoteLine

有一个 $n$ 个点的环，相邻两个点距离是正整数，但是你不知道具体值。

现在有若干个约束，是以下两种其中之一（给定三个参数 $S,T,L$）：

• $S$ 与 $T$ 的顺时针距离不小于 $L$。
• $S$ 与 $T$ 的顺时针距离不大于 $L$。

问环总长的解的方案数。

$n \le 50$。

TODO:

最小生成树

许多题目都需要我们魔改 Prim 或者 Kruskal 算法。但是有些题目这两者都无法解决，这也就引出了第三种算法——Borůvka 算法。尽管该算法本身效率不高，但是它给我们提供了一个新的魔改思路。

Borůvka 算法

一开始每个点自身构成一个连通块。

每一轮，我们找到每个连通块出发到达其它连通块，且边权最小的边。用这些边将连通块合并。若形成环，删掉环上的最大边。

只剩一个连通块时，算法结束。

（图源：Wiki）

每一次都会减少至少一半连通块，迭代轮数 $O(\log n)$。

但是每一轮的计算都比较复杂，常规问题下不及 Prim 和 Kruskal。

最小生成树 例题

#176. 新年的繁荣

一张 $n$ 个点的完全图，每个点 $u$ 有点权 $a_u$（$a_u < 2^m$），两点 $(u,v)$ 之间的边权为 $a_u \land a_v$，$\land$ 表示按位与。求最大生成树。

$n \le 10^5$，$m=18$（$2^{18} = 262144$）。

首先注意到相同点权的点完全可以连在一起，一点浪费都没有。把问题规约到了每种点权只出现一次的情况。

Borůvka 做法

考虑怎么给连通块找出去的最大边。

TODO:

Kruskal 做法

给边排序不太可能，但是我们可以从大到小枚举边权，看看这个边权能不能被拼出来。

问题变为：对于一个指定的 $k$，判断是否存在 $(i,j)$ 不属于同一个集合使得 $a_i \land a_j = k$，然后合并 $i,j$ 所在的集合。

TODO:

Tarjan

CF555E Case of Computer Network (Easy)

给你一个 $n$ 个点 $m$ 条边的图，以及 $q$ 对点 $(s,t)$，让你分配 $m$ 条边的方向。问是否存在一种分配方案，使每对点的 $s$ 能走到 $t$。 

$n,m,q \le 2 \times 10^5$。

边双缩点，每个边双内有环所以必定有解，分配每条边双树的边的方向，树上差分之类的东西随便处理一下就行了。

时间复杂度 $O(n + m + q \log n)$，瓶颈在求 LCA，用四毛子可以优化到完全线性。

2-SAT

有 $n$ 个变量 $x_i \in {0,1}$，有 $m$ 个限制，形如：

• $x_i \circ x_j$
• $\lnot x_i \circ x_j$
• $\lnot x_i \circ \lnot x_j$

其中 $\circ$ 可以取 $\land, \lor, \oplus$ 的任何一个运算符。

我们建 $2n$ 个点：对于每个变量 $x_i$，在图上创建两个点 $x_i = 0$ 和 $x_i = 1$。有向边 $u \to v$ 的含义为 $u \implies v$，即命题 $u$ 能推出命题 $v$。

解法 1：字典序最小解

依次确定 $x_i$ 并 DFS check 有没有和之前的决策出现矛盾，复杂度 $O(n (n+m))$。

虽然效率很低，但是可以求出字典序最小的解（对于这样的问题似乎没有更好的解法）。

Alex_Wei 的博客提到，当 $m = O(n^2)$ 时，可以用 bitset 优化到 $O(\frac {n^3} w)$。

解法 2：缩点

先缩点。若 $u$ 和 $\neg u$ 在同一 SCC 内无解，否则选择拓扑序较大的点，这样一定不会推出另一个。

复杂度 $O(n+m)$，效率很高，但是只能求出一组解。

注意这里的拓扑序一般并不需要拓扑排序，因为 Tarjan 天生带逆拓扑序，Kosaraju 天生带正拓扑序。

2-SAT 例题

第四次忍者大战 (Easy)

有 $n$ 个变量，取值范围是 $1$ 到 $4$，要求下标相邻的两个变量差的绝对值大于等于 $2$，同时有 $m$ 组形如 $(b_1, b_2, \cdots, b_k)$（$k \le 4$）的限制，表示这些变量的取值各不相同。问是否有解。

$n,m \le 10^5$。

首先 $k \le 4$ 相当于明示了直接把这个限制拆开，现在我们只要处理 $x_i \ne x_j$ 这样的限制。

变量的值域不要看成 $[1,4]$，看成二进制的 $[0,3]$ 即 $00,01,10,11$。差的绝对值大于等于 $2$，相当于最高位不同（当然这只是必要条件）。

因此最高位要么是 $\langle 0,1,0,1 \cdots \rangle$，要么是 $\langle 1,0,1,0 \cdots \rangle$，分类讨论一下即可。接下来看最低位。

$01$ 和 $10$ 连着放是不被允许的。再注意到刚才形如 $x_i \ne x_j$ 的限制，我们发现 2-SAT 可以完美地解决。时间复杂度 $O(n + m)$（认为 $k$ 是常数）。

并查集好像也能做吧？但是复杂度多一个 $\alpha$。

[ARC069F] Flags (Normal)

有 $n$ 个变量 $x_i \in {a_i, b_i}$。选择一种赋值方案，最大化：

\[\min\limits_{i \ne j} \lvert x_i - x_j \rvert\]

$n \le 10^4$，值域 $10^9$。

最小值最大，直接二分。设现在二分到的答案为 $len$。

暴力 2-SAT 验证可行性，从 $x$ 向 $[x-len, x-1]$ 和 $[x+1, x+len]$ 这两个区间内的点连边，把所有点按位置排序然后二分即可做到。单次连边数量 $O(n^2)$，过不了。

改用线段树优化建图可以做到 $O(n \log n \log V)$。

题解区有一个 Kosaraju 的 $O(n \alpha(n) \log V)$ 的做法，好像又是序列并查集。

Euler 路

构造！

BZOJ3724 Krolestwo (Hard)

奇偶性相关的图论构造题，可以往 Euler 路去想。

给定一个 $n$ 个点 $m$ 条边的无向连通图 $G$（$m$ 为偶数），其中有 $k$ 个点度数为奇数（$k$ 为偶数）。

找到一种将这 $k$ 个点两两配对的方案，用 $\frac k 2$ 条包含偶数条边的路径连接每一对点，要求 $G$ 上的每条边被恰好覆盖一次（可以经过相同的点）。无解输出 NIE。

$n,m \le 2.5 \times 10^5$。

先考虑路径不一定为偶数条边怎么做。

一个精妙的构造：建一个超级源点，把每个奇点向超级源点连边，问题变为求一条整张图的 Euler 回路。我们称这张图为 $G_1$。

再考虑这个限制。又一个精妙的构造：把每个点拆成两个点放进一个二分图，每走一步都是在二分图的两部左右横跳（当然现在超级源点就只连奇点的左部点）。这张图称为 $G_2$。

能想到这步后面就不难了。

原本 $G$ 的每一条边 $u \leftrightarrow v$ 在 $G_2$ 上现在有两个选择：

• $u_L \leftrightarrow v_R$
• $u_R \leftrightarrow v_L$

我们尝试精心选择之后，依然保证 $G_2$ 所有点的度数都为偶数，这样才能跑 Euler 回路。

发现一个性质：$G_1$ 的每个点度数都是偶数，拆点之后拆出来的两点奇偶性是相同的。$G_2$ 只要一边弄成偶数另一边就是偶数。我们不妨保证 $L$ 这一侧每个点度数都是偶数。

$G$ 上一条 $u \leftrightarrow v$ 的边，现在要么给 $u_L$ 的度数造成贡献，要么给 $v_L$ 的度数造成贡献。我们发现这个问题就是在 $G_1$ 上跑 [AGC035B] Even Degrees。由于 $G_1$ 的总边数是偶数，必定有解，即没有输出 NIE 的情况。做完了。

[AGC018F] Two Trees (Hard)

有两棵大小为 $n$ 的树，两棵树上编号相同的节点拥有相同的点权，但是你不知道具体值。

你要为每个点赋一个点权，使得两棵树上任意一个节点为根的子树内的点权和的绝对值为 $1$。输出一个方案或报告无解。

$n \le 10^5$。

首先有一个观察，$\lvert x \rvert = 1 \implies x \bmod 2 = 1$。这样就确定了每个点的点权奇偶性（而且和度数的奇偶性是一样的），如果出现矛盾就无解。

度数奇偶性不难想到 Euler 回路，开始构造。

对于奇点，我们把两棵树上编号相同的连起来，偶点什么都不做。这张图称为 $G$。$G$ 上所有点的度数都是偶数，存在 Euler 回路。

对于一个子树，有三种情况：

• 欧拉回路从一个奇点出去了。
• 欧拉回路从一个奇点进来了。
• 欧拉回路经过了父亲。

前两种情况是成对出现，但是有一个落单的（可能是第一种也可能是第二种）和第三种配对。

第三种不太好刻画，我们考虑让第三种为 $0$ 然后前两种互相抵消。我们令从第一棵树到第二棵树的奇点点权为 $1$，反之为 $-1$，偶点为 $0$。

做完了。