2025 北京 - 2.5 graph

Problem Set

CF2057E2 Another Exercise on Graphs (hard version)

先把初始所以边权变成 $0$，容易发现可以对边从大到小排序，然后每次逐次把边的边权 $w$ 改成 $1$，跑个全源最短路，此时 $dis_{i,j}$ 表示在 $(i,j)$ 间的所有路径中，边权 $w$ 的最小排名 -1。于是我们就可以在 $\mathcal O(m^2n\log n)$ 的时间复杂度解决 E1。

发现把 $0$ 改成 $1$ 非常不好做，正难则反，试着把 $0$ 改成 $1$。每次把一条边改成 $0$，那么把两个点用并查集连起来，连通块里的每对点的距离都是 $0$，如果对整个全源最短路有影响当且仅当连通了两个新的连通块，所以只有 $n$ 条边是有用的，现在时间复杂度为 $\mathcal O(mn^2\log n)$。每次更新重新跑 dij 太浪费了，考虑 Floyd，只要更新的时候以改的那条边为中转边就好，时间复杂度 $\mathcal O(n^3)$。

CF822F Madness

CF1698F Equal Reversal

欧拉回路的方法我看不懂啊！讲讲普通的。

首先每次交换不会改变整个序列的相邻二元组集合，这个可以用欧拉回路理解，翻转等于反向一个欧拉回路。这里我们断言：如果两个序列首尾相同且二元组集合相同，那是一定可以被操作的。判断完考虑构造性证明这个东西：

从左往右找到第一个不同的下标 $i$，令 $u=s_{i-1}=t_{i-1},x=s_i,y=t_i$，如果 $s$ 后面存在 $xu$ 或者 $t$ 后面存在 $yu$ 就可以直接交换，因为操作可逆。否则两个字符串一定能达到一个中间状态：能找到一个 $c$，使得 $s,t$ 中都存在 $cu$，这个可以根据二元组集合相同可以鸽巢原理证一下。

CF843D Dynamic Shortest Path

考虑直接跑 dij 浪费在哪里：观察到每次只会让边权加一，所以整个最短路的增量非常小，且整个 dij 因为需要快速找到最小距离的点，所以需要优先队列的一个 $\log$。利用这个事情，我们对增量的边权跑最短路，跑完得到每个点最短路比原来的多的距离，因为值域最多 $10^6$，所以不用优先队列，放到一个值域桶里面扫就是对的。

CF1458D Flip and Reverse

观察到等价于在翻一个欧拉回路，这里贪心就好了。

[HNOI2019] 校园旅行

考虑暴力 dp：令 $f_{u,v}$ 表示 $u$ 到 $v$ 有没有合法路径，暴力松弛就是 $\mathcal O(m^2)$ 的。发现权值只有 $0,1$，所以很多边没有用：对于一个同色连通块，如果是二分图可以保留其一棵生成树，否则加一个自环；对于只有异色边构成的连通块，一定是二分图，也保留一棵生成树就好了。

CF750H New Year and Snowy Grid

题目等价于判断双联通，不是很好搞，正难则反判定割集。相当于最多加一个 #，使得左下角和右上角的障碍八联通。因为每次询问的 $k\le 10$，所以我们关心的连通块可以暴力枚举，这里用可撤销并查集怎么维护都行，我的时间复杂度为 $\mathcal O(qd^2k^2)$，其中 $d=8$。

CF718E Matvey’s Birthday

考虑如何刻画两个点之间的距离，如果把一条路径按照跳跃同色边切开（只保留走 $|i-j|=1$ 的边），就是一个个区间，令 $f_{i,j}$ 表示 $i$ 到颜色 $j$ 的最短路，$u,v$ 的答案就是 $\min(|u-v|,\min\limits_{c}f_{u,c}+f_{v,c}+1)$，前面那项是不存在跳跃同色边，特判一下。

自然的根据两个大小分讨：发现最大直径不超过 $15$，所以如果 $|u,v|\le 15$ 直接暴力，否则上面式子一定取后面那一项。但是还是避免不了枚举 $u,v$：发现本质不同的 $f_u$ 很少，具体的，令 $g_{x,y}$ 表示从任意颜色为 $x$ 的点到任意颜色为 $y$ 的点的最小代价，则有 $f_{u,x}-g_{x,y}\in\{0,1\}$。所以可以把前面所有数的状态压起来统计，时间复杂度 $\mathcal O(nk^22^k)$。Alex_Wei 在题解区提出了一个爆标做法，到时候补一补。