题单链接 ZR 2026 Summer C 8.10 ZR 2026 Summer C 8.11

旅行者 (洛谷-P5304)

是神秘小做法！

非常不容易想到，我们对 $k$ 个点进行分组，具体分组方式如下：

• 枚举二进制位 $i$ ；
• 对第 $i$ 位是 0/1 进行分组；
• 建立虚拟源点 s ，连有向边至其中一组的每个点，边权为0；
• 建立虚拟汇点 t ，另一组中每个点连有向边至 t，边权为0；
• 从 s 到 t 跑最短路，记录到最小值答案中；
• 交换这两组重新建边跑最短路。

正确性显然，因为如果 $u$ 到 $v$ 为最短的，它们肯定至少有1位不同，被分到了不同组。

最大半连通子图 (洛谷-P2272)

容易发现一个边双连通分量是一个半连通子图。而缩点后，最长的链即为最大半连通子图。

至于答案，使用拓扑排序+DP。

设 $f_i$ 表示以 SCC $i$ 结尾的最长链的点权和，设 $g_i$ 表示以 SCC $i$ 结尾的最长链的方案数。

转移方程（假设存在边 $(u,v)$）：

若 $f[u] + \text{size}[v] > f[v]$：

若 $f[u] + \text{size}[v] == f[v]$：

注意去重。

Telephone Lines S (洛谷-P1948)

考虑二分答案最小支出 $x$。

因为有 $k$ 次免费的机会，所以实际上花费是 $1$ 到 $n$ 路上第 $k+1$ 大的边的权值。

所以我们重新给边赋值，$>x$ 的赋值为 1 ，$\le x$ 的赋值为 0，跑一遍最短路即可。如果最短路长度 $l$ $>k$ 则说明答案更大，否则说明答案更小。

加工零件 (洛谷-P5663)

发现若存在一条从 $1$ 到 $u$ 的长度为 $l$ 的路径，那么一定存在一条长度为 $l+2$ 的路径（因为路径可以重复经过），但是不一定存在长度为 $l+1$ 的路径。

所以分奇偶计算最短路即可。