前言

本文为洛谷省选计划 2021 Week 4 的做题记录。

每道题的超链接后面都有该题的通过状态，其中 AC 表示已经通过，NC 表示未完成。

正文

题解：

考虑二分，问题转化为是否能用 nn 条路径覆盖整张 DAG\mathcal{DAG}，路径之间允许相交。

这是一个经典问题，我们对原 DAG\mathcal{DAG} 跑传递闭包，转化为路径之间不允许相交的情况，这个将每个点 uu 拆为两个点 u1,u2u_1, u_2，对于原图的边 u→vu \to v，在新图上连边 u2→v1u_2 \to v_1，答案即为原图节点数 - 新图最大匹配。

代码实现

题解：

考虑对所有点权建 Trie\mathcal{Trie} 树，把所有点的虚树拿出来，可以发现对于虚树上的 n−1n - 1 个 LCA\mathcal{LCA}，其左右两颗子树刚好对应两个连通块，那么我们仅需对于每一个这样的 LCA\mathcal{LCA}，求出连接其对应的两个连通块的边权即可。

显然在最优方案下，这样的边权仅会在后若干位有值，也即我们无需关心这些 LCA\mathcal{LCA} 的祖先，仅需关心如何在它们的子树中决策，那么问题变为：给定一颗 Trie\mathcal{Trie} 树，在它的根节点的左右子树各选出一个权值，求二者异或的最小值。这个按位贪心决策即可，复杂度实际上相当于对整颗 Trie\mathcal{Trie} 树进行启发式合并，为 O(nlog⁡2nlog⁡2w)\mathcal{O}(n\log_2n\log_2 w)，ww 为值域。

代码实现

题解：

海拔的限制让我们联想到用于求解最大生成树的 Kruskal\mathcal{Kruskal} 算法：每个时刻其维护的连通块都是由所有权值大于某个数的边构成的。方便起见，我们建出 Kruskal\mathcal{Kruskal} 重构树，这样能够开车经过的边必然形成若干颗子树。

我们发现 Yazid 能够开车的范围仅为出发点所在的一颗子树，子树的根我们可以通过倍增找出，那么剩下的问题就在于如何求点 11 到整颗子树的最短路，这个用 Dijkstra\mathcal{Dijkstra} 预处理，然后维护子树最小值即可。

代码实现

题解：

这是一个不需要用到 WQS\mathcal{WQS} 二分的做法，但用到了这个问题具有的凸性。

考虑给每个点赋上一个点权，表示其与 ss 之间的所有连边的最小边权（如无连边则赋为正无穷），那么选择这个点权相当于选择了这条边，接下来我们就可以忽略 ss 了。

对于去掉 ss 后的图，我们求解其最小生成森林，那么显然选择不在该森林内的边不优，我们删除它们。

在每颗树中，我们初始时必须要选择一个点（否则会导致生成树不联通），显然选择点权最小的点会最优。

设 fi,jf_{i, j} 表示在第 ii 颗树中选择 jj 个点的最小答案，转移可以根据凸性贪心增量，即往 fi,j−1f_{i, j - 1} 对应的方案中加入一个新点使得 fi,jf_{i, j} 最小。

设加入新点为 uu，它会与某个点 vv 形成一个环，那么点 uu 的贡献为点 uu 的点权减去点 uu 与点 vv 之间的路径上的最大边权。当然，加入新点 uu 后要删去这条边。

由于 fi,jf_{i, j} 具有凸性，因此我们可以考虑计算每一个差分 fi,j−fi,j−1f_{i, j} - f_{i, j - 1}，然后取前 kk 个即可得到答案。

现在考虑每个点的贡献，也就是每个点加入时会对应地删去哪条边。不妨考虑每条边会被哪个点删掉。

从小到大考虑所有边，设当前的边的两个端点所在的在两个连通块中最小的点权分别为 aa 和 bb，那么当 aa 和 bb 中的较大值对应的点被选中时，当前的边就会被这个点删除。这个我们在用 Kruskal\mathcal{Kruskal} 算法求解最小生成森林的同时，在并查集上维护当前连通块的最小值即可。

注意无解情况有：图不连通、至少需要连的边大于 kk 条以及至多能够连的边小于 kk 条。

代码实现

题解：

我们很容易对题目建立出最小割的模型，但用网络流求解的时间复杂度是无法接受的。

考虑这样一个经典套路：平面图最小割转化为对偶图最短路（实际上二者可以互相转化）。

什么是对偶图？我们考虑将平面图外左下角的平面看做源点 SS，右上角的平面看做汇点 TT，将平面图中的每一个平面都看做一个节点，将有边相交的平面所对应的节点之间连无向边，边权为该边的权值，这样形成的一张图被称作原图的对偶图。这里可以看到样例所对应的图和其对偶图。

可以发现，对偶图中每一条 SS 到 TT 的路径都对应了原图中的一个割集，因此我们求解对偶图中 SS 到 TT 的最短路，就等价求解原图的最小割。

代码实现

题解：

我们考虑将每一条边定向：设一条边的两个端点分别为点 uu 和点 vv，那么若点 uu 的度数不等于点 vv 的度数，则由度数小的点连向度数大的点，否则由编号小的点连向编号大的点以保证偏序关系。

定向后，我们枚举每一个点 uu，枚举点 uu 的后继 vv，再枚举点 vv 的后继 ww，若存在有向边 u→wu \to w，则我们找到了一个三元环。显然这样是不会算重或算漏的。

我们接下来证明这个算法的时间复杂度是 O(mm)\mathcal{O}(m\sqrt{m}) 的。

设点 uu 的出度为 outuout_u，显而易见的是答案即为 ∑i=1moutvi\displaystyle \sum_{i = 1}^m out_{v_i}。对于出度不超过 m\sqrt{m} 的点，它们对时间复杂度的贡献至多为 O(mm)\mathcal{O}(m\sqrt{m})。对于出度大于 m\sqrt{m} 的点，由于它必然会连向出度不小于其本身的点，且总的出度是 O(m)\mathcal{O}(m) 的，因此它们的出度都是 O(m)\mathcal{O}(\sqrt{m}) 的，它们对时间复杂度的贡献同样至多为 O(mm)\mathcal{O}(m\sqrt{m})。因此，该算法的时间复杂度即为 O(mm)\mathcal{O}(m\sqrt{m})。

代码实现

题解：

注意题面里有一点没有写明：修改后的物流系统仍然需要满足从任何物流基站都能将物资运往控制基站。

设点 ii 到点 11 的最短路长度为 disidis_i，基环树的环长为 mm，那么答案即为 ∑i=1nkdisi⋅ci1−km\dfrac{\displaystyle \sum_{i = 1}^n k^{dis_i}\cdot c_i}{1 - k^m}，根据其我们可以发现，若我们要改变一个点的后继，我们一定会将这个点的后继改为点 11。

若我们忽略答案的表达式的分母，那么我们可以做一个树形 DP\mathcal{DP}：设 fu,i,jf_{u, i, j} 表示在以点 uu 为根的子树内，已经改变了 ii 个节点的后继，且有 disu=jdis_u = j，答案的表达式的分子的最大值。转移不难。

如何在做 DP\mathcal{DP} 的时候把环长记入状态呢？由于点 11 的后继是不变的，因此环一定形如 1→s1→ss1→⋯→11 \to s_1 \to s_{s_1} \to \cdots\to 1，且除去点 11，其它点的深度是沿环递减的，因此我们在状态中记录当前环的长度，转移时分讨是继续环还是结束环即可。

不过这个做法需要卡一卡空间，具体地，把 DP\mathcal{DP} 数组用 vector\texttt{vector} 存储，然后对状态的每一维的上下界进行限制即可。

代码实现

题解：

我们先求出最小生成树，然后枚举每一条非树边并尝试将其加入生成树中。

在加入当前枚举到的非树边时，我们需要删掉环上的一条边，这条边的边权必须尽量大，同时又要严格小于加入的非树边。

这个可以用树上倍增来维护，维护边权的最大值和严格次大值即可。

代码实现

题解：

我们知道最小生成树具有性质：对于一张图的所有最小生成树，具有相同边权的边的出现次数相同。

每种边权的边是独立的，我们可以分别算方案数，然后根据乘法原理将方案数乘起来。

注意到每种边权的边不会超过 1010 条，因此暴力枚举的复杂度是可以接受的。对于一种边权的方案数，我们先将最小生成树上其它边权的边加入，然后再暴力枚举当前边权的边的集合并判断是否合法即可。

当然，还存在不需要暴力枚举边的集合的做法：先将所有当前边权的边和最小生成树上其它边权的边加入图中，然后对后者缩点，再对缩点后的图跑矩阵树定理。复杂度证明可以参考这篇题解。

代码实现

题解：

对一个固定的 bb，判断其是否合法并不好做，我们不如换个角度思考：用 x1∼nx_{1 \sim n} 的线性组合去求 bb 的可能值。

设 fif_i 表示 1∼i1 \sim i 内有 fif_i 个数合法，答案即为 fr−fl−1f_r - f_{l - 1}，那么问题就在于如何求 fif_i。

接下来就是同余最短路的模板题了。

考虑任选一个 aia_i 作为模数，记其为 pp（注意这里不能选择 00 作为模数）。

对于一个合法的 b=p⋅q+r (q∈N,r∈[0,p))b = p \cdot q +r ~(q \in \N, r \in [0, p))，它会使得所有 b=p⋅(q+s)+r (s∈N)b =p \cdot (q + s) + r ~(s \in \N) 均合法。在 1∼i1 \sim i 的范围内，这一类的数共有 ⌊i−(p⋅qmin⁡+r)p⌋+1\lfloor \dfrac{i - (p \cdot q_{\min} +r)}{p} \rfloor + 1 个。

那么问题转化为求 p⋅qmin⁡+rp \cdot q_{\min} +r。

考虑最短路，设 dispdis_p 表示上述表达式，那么我们由点 u (u∈[0,p))u~(u \in [0, p)) 向所有 (u+aj) mod p (j∈[1,n],aj≠p)(u + a_j) \bmod p~(j \in [1, n], a_j \ne p) 连一条权值为 aja_j 的有向边，然后以点 00 为源点跑单源最短路经即可。

实现时最好是取 aia_i 的最小值作为模数，这样图的规模是最小的，常数也是最小的。

代码实现

题解：

实际上两种限制的形式是类似的：若其中一个位置选择了一个特定的字母 aa，那么另外一个位置就必须或不能选择一个特定的字母 bb。由于这个限制是二元的，因此我们考虑 2−SAT\mathcal{2-SAT}。

考虑对每个位置能够选择的两个字母建点，对于位置 ii 设其为 ui,viu_i, v_i。第一条限制是很好表示的，第二条限制也仅需特判一下即可。

对于没有限制的位置可以考虑 O(2d)\mathcal{O}(2^d) 地枚举其限制。

代码实现

题解：

答案呈分式的形式，限制分子或分母都不好做，我们不妨考虑分数规划。

这样问题就转化为了求解完全二分图上的最大权完美匹配，用 KM\mathcal{KM} 算法或最大费用最大流解决均可。

代码实现

题解：

可以发现如果建出广义圆方树，那么对于点 uu 和点 vv，能够断掉它们的点即为两点之间的路径上的圆点个数减去被路径上被占领的圆点个数。

所以建出广义圆方树，对于每一次询问，在构建询问点的虚树的过程中维护答案即可。

当然也可以不用建虚树。我们考虑将所有询问点按照 dfnudfn_u 排序，然后环形遍历相邻的两个询问点并求出它们路径上除 LCA\mathcal{LCA} 外的圆点个数 cntcnt。由于除 LCA\mathcal{LCA} 外，每个点恰好会被经过两次，所以答案即为 cntcnt 的总和除以 22 减去询问点的个数。当然，还要判断序列的第一个点和最后一个点的 LCA\mathcal{LCA} 是否为圆点，是则还需要把它的贡献加上。

代码实现

题解：

建图是简单的，用最大权闭合子图或者最小割分析都可以。

构造方案的话，我们考虑求出所有源点 SS 能够到达的点，这些点要么表示已经被选择了的实验，要么表示已经被选择了的仪器，所以这些点就是最大权闭合子图中的点。

代码实现

题解：

注意到贡献具有依赖性，因此我们可以考虑用最小割来解决问题。

先假设每个人既选了文科又选了理科，把所有的贡献加上，那么我们需要最小化减去的贡献。

首先对第 ii 行第 jj 列的同学建点 ai,ja_{i, j}，将源点 SS 向其连边，容量为选文科的满意值，将其向汇点 TT 连边，容量为选理科的满意值。这样，二者一定会被割掉其一，表示不选择对应的科目。

对于同时选文科的贡献，我们考虑建点 bi,jb_{i, j}，将源点 SS 向其连边，容量为同时选文科的满意值，将 bi,jb_{i, j} 向涉及到的所有 ai,ja_{i, j} 连边，容量为 +∞+\infty。这样，如果最终的贡献包含同时选文科的贡献，则这些同学向汇点的连边（也即表示选理科的连边）都会被割掉。同时选理科的贡献也是同理的。

这样，我们跑一遍最大流，求出最小割，即为减去的贡献。

代码实现

题解：

先考虑处理第一条限制，我们可以建立一个最小割模型：对于所有 i∈[1,p],j∈[1,q],k∈[1,r]i \in [1, p], j \in [1, q], k \in [1, r]，我们建点 ai,j,ka_{i, j, k}。将源点 SS 向所有 ai,j,1a_{i, j, 1} 连边，容量为 +∞+\infty，将所有 ai,j,ka_{i,j, k} 向 ai,j,k+1a_{i, j, k +1} 连边，容量为 vi,j,kv_{i, j, k}，表示 fi,j=kf_{i, j} = k 的贡献，将所有 ai,j,ra_{i, j, r} 向 TT 连边，容量为 vi,j,rv_{i, j, r}，表示 fi,j=rf_{i, j} = r 的贡献。对这张图求最小割，那么每一组 i,ji, j 都会选择一个 fi,jf_{i, j}，这样我们就能够得出不考虑第二条限制的答案了。

再来考虑处理第二条限制，可以发现限制本质上只有 fi,j−fi′,j′≤df_{i, j} - f_{i', j'} \le d。不妨假设 fi,j=k,fi′,j′=lf_{i, j} = k, f_{i', j'} = l，那么有 l∉[1,k−d)l \notin [1, k - d)，为了处理这条限制，我们考虑加入一条边，使得当 l∈[1,k−d)l \in [1, k - d) 且 ai,j,k→ai,j,k+1a_{i, j, k} \to a_{i, j, k +1} 和 ai′,j′,l→ai′,j′,l+1a_{i', j', l} \to a_{i', j', l+ 1} 两条边被割掉时，图中仍然存在一条 SS 到 TT 的路径。问题分析到这里已经很明显了，我们将 ai,j,ka_{i, j, k } 向 ai′,j′,k−da_{i', j', k - d} 连边，容量为 +∞+\infty 即可。

据说这玩意叫做离散变量模型。

代码实现

题解：

直接套用有源汇上下界最小费用可行流的做法是简单的，但还存在其它的做法。

每颗行星被访问恰好一次的限制令我们想到拆点，我们将第 ii 颗行星拆为 i1i_1 和 i2i_2 两个点。

不妨考虑每颗行星被访问时的贡献。

可以发现，一颗行星要么被空间跳跃到，要么被某颗行星走到，一颗行星被访问到的贡献仅和这两者有关，而和它后面走到的行星无关。我们考虑从这里入手建模。

首先由所有 i2i_2 向汇点 TT 连一条容量为 11、费用为 00 的边，表示每个点需要被访问一次。

对于前者，我们由源点 SS 向所有 i2i_2 连一条容量为 11、费用为 aia_i 的边，表示空间跳跃到第 ii 颗行星。

对于后者，我们对每条星际航路按照行星的引力值大小定向，并由起点的 i1i_1 向重点的 i2i_2 连一条容量为 11、费用为航行时间的边，表示走一条星际航路。为了提供流量，我们还需由源点 SS 向所有 i1i_1 连一条容量为 11、费用为 00 的边。

这样，由于该模型的最大流为 nn，因此我们跑最小费用最大流即可得到正确的答案。

代码实现

题解：

可以发现合法的解一定能够被分为 kk 组，满足每组内的区间互不相交，那么我们用 11 流量来表示选择一组区间，然后限制最大流不超过 kk 即可。

具体地，设源点和汇点分别为点 SS 和点 TT，把左闭右开区间离散化后，设离散化后最大值为 lenlen，那么我们由点 SS 向点 11 连一条容量为 kk、费用为 00 的边，由所有点 ii 向点 i+1i + 1 以及点 lenlen 向点 TT 分别连一条容量为 +∞+\infty、费用为 00 的边。对于每一个左闭右开区间 [l,r)[l, r)，我们从 ll 向 rr 连一条容量为 11、费用为 r−lr - l 的边，表示选择这个区间的贡献。

对这个模型跑最大费用最大流即可。

代码实现

题解：

第一问直接 O(n2)\mathcal{O}(n^2) 做即可。

第二问考虑最大流建模，ii 向 jj 连边当且仅当 fi+1=fjf_i +1 = f_j，源点 TT 向 fi=1f_i = 1 的位置连边，fi=sf_i = s 的位置向汇点 TT 连边，注意要拆点。

第三问把源点 SS 向位置 11 的连边、位置 nn 向汇点 TT 的连边（如果存在）以及位置 11 和位置 nn 的流量都设为 +∞+\infty 即可，注意要特判 s=1s = 1 的情况。

代码实现

题解：

最大权闭合子图的经典问题。

注意最初建出来的图不一定是 DAG\mathcal{DAG}，因此我们要在反图上跑拓扑排序，只有遍历到的点才能够拿出来做。

代码实现

题解：

每天的人数限制让我们想到上下界网络流，那么我们可以考虑建图：由所有 ii 向 i+1i +1 连一条容量为 [ai,+∞][a_i, +\infty]、费用为 00 的边。

这样建图，根据传统的有源汇网络流的套路，我们可能会想到由源点 SS 向 sis_i 连边，由 ti+1t_i +1 向汇点 TT 连边的做法，但这样连边显然是错误的，因为如果路径之间存在交叉，可能会产生一些不存在的贡献。

我们不妨考虑无源汇的网络流 ：对于志愿者 ii，由 ti+1t_i +1 向 sis_i 连一条容量为 +∞+\infty、费用为 cic_i 的边。这样，志愿者的贡献就可以用循环流来表示，并且不会出现上面所述的产生不存在的贡献的情况。

对这个模型跑无源汇上下界最小费用可行流即可。

题解区说这题还有从线性规划角度分析的做法，完全不会！

代码实现

题解：

问题转化为求总等待时间的最小值。

注意到对于一位技术人员，假设他修倒数第 ii 辆车所需的时间为 ww，那么其对答案的贡献即为 w⋅iw \cdot i。

这样建图就很简单了：我们对每辆车建点，以及对每位技术人员修的倒数第若干辆车建点，将它们之间连边，费用为对应的贡献。对这个模型跑最小费用最大流即可。

代码实现

未完待续 ……