CF1307G 题解

· · 题解

由于其余题解在线性规划转对偶部分描述的缺失，本题解主要针对于将图上的线性规划转化成纯线性代数形式，随后自然转化为对偶形式，总的来说是对其余题解的补充和延伸。
用关联矩阵将网络流语言转换成线性代数语言后就能显见地取对偶了，这点的直观性是配凑等方法所不具有的。

阅读本题解需要一些线性代数的知识。推荐先阅读 2021 年 dxm 的集训队论文《再探线性规划对偶在信息学竞赛中的应用》，同时可以阅读本文获取可能的前置知识。

我们使用斜粗体 \bm a 表示一个向量，\bm 0, \bm 1 分别表示全 0 和全 0 的向量，维数视上下文而定。对于一个向量 \bm v，我们令 v_i 表示其第 i 维的取值，维度从 1 开始编号。

考虑令 d_u 为差分意义下的最短路，即 d 序列需要满足 d_u - d_1 为 1 \to u 的最短路长度。设 w_{u, v} 为 u\to v 的边的边权，x_{u, v} 为 u\to v 增加的边权。然后可以写出线性规划：

\max_{d, x} \quad & d_n - d_1 \\ \text{s.t.} \quad & d_v \le d_u + w_{u, v} + x_{u, v} \\ & \sum_{u, v} x_{u, v} \le k \\ & x_{u,v} \ge 0 \end{aligned}

自然地，我们考虑构造限制矩阵。我们令 M 为对应图的 m\times n 关联矩阵，其元素取值满足 (u,v) 有一条边 i 则 M_{i,u} 减 1, M_{i, v} 加 1。令 \bm d 为差分最短路对应的 n 维向量，\bm x 为每条边增加边权对应的 m 维向量，\bm w 为原边权对应的 m 维向量。和上方的限制条件进行对照后不难可以构造出如下的限制：

\begin{aligned} \max_{\bm d, \bm x} \quad & (-1, 0, \dots, 0, 1, 0, \dots, 0) \begin{bmatrix} \bm d \\ \bm x \end{bmatrix} \\ \text{s.t.} \quad & \begin{bmatrix} M &- I_m \\ \bm 0 &\bm 1 \end{bmatrix} \begin{bmatrix} \bm d \\ \bm x \end{bmatrix} \le \begin{bmatrix} \bm w \\ k \end{bmatrix},\ \begin{bmatrix} \bm d \\ \bm x \end{bmatrix}\ge \bm 0 \end{aligned}

其中 -I_m 是 m\times m 单位矩阵每个元素取相反数后得到的矩阵，\bm l = (-1, 0, \dots, 0, 1, 0, \dots, 0) 是一个 m + n 维向量，其中 l_1 = -1,\ l_n = 1，其余分量均为 0。得到标准形式后不难转对偶：

\begin{aligned} \min_{\bm y} \quad & \left[\bm w\quad k\right] \bm y \\ \text{s.t.} \quad & \begin{bmatrix} M^{\mathsf T} &\bm 0 \\ - I_m &\bm 1 \end{bmatrix} \bm y \ge \bm l,\bm y \ge \bm 0 \end{aligned}

注意这里 \bm y 是个 m + 1 维的向量。根据互补松弛性取等。自然展开，设 y = [\bm \alpha \ \ \beta]，其中 \alpha_{u, v} 表示 u\to v 的边对应的变量。得到如下的线性规划：

\min_{\bm y} \quad & \sum_{(u, v)} w_{u,v} \alpha_{u,v} + \beta k \\ \text{s.t.} \quad & \forall 1<u<n, \ \sum_{v} \alpha_{u, v} - \sum_{v} \alpha_{v, u} = 0 \\ & \sum_{v} \sum_{v} \alpha_{v, 1} - \alpha_{1, v} = -1 \\ & \sum_{v} \sum_{v} \alpha_{v, n} - \alpha_{n, v} = 1 \\ & \beta \ge \alpha _{u, v} \end{aligned}

到这里就是大部分题解所进行的转化了。若将 \alpha_{u, v} 看作流量，则流量上界均是 \beta。不妨令 \alpha_{u,v} \in [0, 1]，令单位流为 f = 1 / \beta，改写为

\min_{\bm y} \quad & \frac{\sum_{(u, v)} w_{u,v} \alpha_{u,v} + \beta k}f \\ \text{s.t.} \quad & \forall 1<u<n, \ \sum_{v} \alpha_{u, v} - \sum_{v} \alpha_{v, u} = 0 \\ & \sum_{v} \sum_{v} \alpha_{v, 1} - \alpha_{1, v} = -f \\ & \sum_{v} \sum_{v} \alpha_{v, n} - \alpha_{n, v} = f \\ & \alpha _{u, v} \in[0, 1] \end{aligned}

由于答案对 f 单调，因此当 f\in [s, s + 1](s \in \mathbb Z) 时目标函数的最值肯定出现在边界，这时 \alpha_{u,v} 的值也是整数。于是我们只需要直接建图跑网络流，对答案枚举取值后取 \max 即可。

总时间复杂度 O(\text{Dinic}(n, m) + qn)。

Submission.