自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 22:43:11，当前版本为作者最后更新于2022-11-26 19:22:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

先说一点题外话. 原本以为开放题解之后就会有人来提交简单题解, 没想到一个星期过去了还是各种主席树云云. 明明这题没那么麻烦. 或者说有简单的做法, 虽然正确性还是需要一点思考.

题意

有一张 $n$ 点 $m$ 边有向图, $q$ 次修改. 每次修改是给出原图中一条边, 如果把它删掉之后仍然存在 $1$ 到 $n$ 的道路, 则把它删掉, 否则什么都不做. 如果这条边已经被删掉了, 那么也什么都不做.

你需要对每次修改输出是否删掉了这条边. $n, m, q \leqslant 2 \times 10^5$.

分析与解答

我们是一定要离线做的 (不然就真的是动态图连通性了, 约等于不能做).

首先我们发现, 如果一条边被多次试图删除, 那么后面那次肯定是没有用的.

因为如果第一次删除它就成功删除, 那么第二次删除的时候会什么都不做. 如果第一次删除它发现没法删除, 那说明它是从 $1$ 到 $n$ 的必经之路. 而整个修改过程中边只会越来越少, 所以第二次删除的时候它一定也是必经之路. 因此第二次也不会删除它.

综上所述, 我们可以假设每条边只会被删除一次. 设第 $i$ 条边被删除的时间是 $d_i$. 如果没被删除过, 就设 $d_i = \infty$ 或者说 $d_i = q + 1$.

我们来考虑所有修改都执行完毕之后, 还剩下的从 $1$ 到 $n$ 的路径是哪一条. 如果我们能求出这条路径, 那么在路径上的边都不会被删除, 不在路径上的边都会被删除 (因为删了还是有这条路径).

这条路径应该满足什么性质呢?

首先, 比较容易看出来的是, 这条路径上 $d_i$ 最小的边要尽量大. 因为我们如果把所有的从 $1$ 到 $n$ 的路径都列出来, 那么最先走不通的是最小 $d_i = 1$ 的路径, 然后是最小 $d_i = 2$ 的路径, 依此类推, 最后只剩下最小 $d_i$ 最大的这些路径.

其次, 在所有这样的路径中, $d_i$ 次小的边也要尽量大. 道理和之前相同.

依此类推, 我们可以把比较的规则总结为: 把每条路径上的边的 $d_i$ 从小到大排列, 我们需要找到得到的排列字典序最大的路径.

我们设 $P_i$ 是从 $1$ 到 $i$ 的最优路径, 定义两条路径之间的大小就是上面的比较方法, 也就是说把经过的 $d_i$ 从小到大排序后比较字典序.

如果我们截止到这一步, 那么可以把每条路径的边权, 或者说“排列”, 用主席树存储来比较, 详见其他题解. 不过事实上我们有更容易的方法.

如果你不想看证明或者想自己思考证明, 请跳到下面加粗的综上所述的位置.

为了叙述方便, 我们想象, 这个问题相当于把每条边的边权定为 $10^{q-d_i}$, 然后选取最短路. 对那些每删除的边, 我们设边权是 $0$. 比如说 $q = 4$,

如果我们经过了 $d_i = 2, 3$ 的边, 路径长就是 $110$.

如果我们经过了 $d_i = 2, 4$ 的边, 路径长就是 $101$, 比前面那个短.

我们使用 Dijkstra 算法, 设 $1$ 到 $i$ 的最短路长度为 $dis_i$. 不过我们不可能真的用高精把这个东西算出来, 只是方便我们分析.

假设 Dijkstra 进行到某个时刻. 我们要考虑那些起点已经被扩展出来, 终点还没有被扩展出来的边, 选取其中 $dis_{\text{起点}} + 10^{q-d}$ 最小的一个, 并以此扩展其终点.

由于这个原因, 我们需要比较两条边的 $dis_{s_1} + 10^{q-d_1}$ 和 $dis_{s_2} + 10^{q-d_2}$ 的大小.

• 如果 $s_1 = s_2$, 显然我们只需要比较 $d_1$ 和 $d_2$.
• 否则, 我们假设 $dis_{s_1} < dis_{s_2}$ (反过来也一样, 我就不写两遍了).
• 由于 Dijkstra 是按 $dis$ 从小到大扩展点, 而 $s_2$ 已经扩展出来了, $dis_{s_1} + 10^{q-d_1}$ 那个点还没扩展出来, 我们一定有 $dis_{s_1} + 10^{q-d_1} > dis_{s_2}$.
• 由于每条边的 $d$ 都是唯一的, $dis_{s_1}$ 和 $dis_{s_2}$ 中都肯定没有 $10^{q-d_1}$ 这一位 (因为有这一位的路径都经过了 $d_1$ 对应的边, 但是 $d_1$ 对应的这条边的终点我们还没扩展出来呢).

综上, $dis_{s_1}$ 与 $dis_{s_2}$ 一定长这样:

$$\begin{aligned} dis_{s_1} &= {\color{red}\text{xxx}}{\color{blue}0}{\color{green}\text{aaa}}\\ dis_{s_2} &= {\color{red}\text{xxx}}{\color{blue}0}{\color{green}\text{bbb}}\\ dis_{s_1} + 10^{q-d_1} &= {\color{red}\text{xxx}}{\color{blue}1}{\color{green}\text{aaa}}\\ \end{aligned}$$

其中三个红色的 xxx 都是相同的数字, 而 aaa 和 bbb 位数相同, aaa 小于 bbb; 蓝色的 0/1 就是 $10^{q-d_1}$ 所在的位.

因此不难看出, 如果我们把 $dis_{s_2}$ 也加上某个 $10^{q-d_2}$, 那么加上的这个 1 如果落在绿色位置, 也就是 $d_1 < d_2$ (注意我们的边权选取导致这个加法不可能进位), 加完之后也比 $dis_{s_1} + 10^{q-d_1}$ 更小; 如果落在红色或者蓝色位置, 也就是 $d_1 \geq d_2$, 加完一定比 $dis_{s_1} + 10^{q-d_1}$ 更大.

综上所述, 我们在 Dijkstra 的时候只需要比较最后走出的这一步的 $d_i$, 选取 $d_i$ 较大的一个; 而在 $d_i$ 相同时比较上一步的 $dis$ 即可.

事实上, $d_i$ 相同的情况只会在 $d_i = \infty$ 的时候发生. 不过由于没被删的边我们可以任意处置, 可以假想这些边在第 $q+1, \dots, q+m$ 次也依次被删除了, 所以这种情况其实可以随便认为谁更大谁更小, 都不需要比较上一步的 $dis$.

(真的要比较也不难, 因为我们不需要实际求出 $dis$, 只需要比较两个点在 dijkstra 过程中谁先被扩展出来, 谁的 $dis$ 就更小.)

我们记录每个点的最短路的前驱, 最后就可以找出 $1$ 到 $n$ 具体的最优路径了.

最初的想法

事实上, 这个解法是我在手玩了自己随便写的几个数据之后想到的, 并且最开始也不会有这些复杂度证明, 只是一个简单的贪心想法.

如果我们有了这个想法, 试图证明它也不是困难的, 读者也可以自己试着证一下. 核心思路就是假设有一条道路比这样求出的更优, 然后想一想 Dijkstra 中哪一步走不通. 如果没有想法, 也可以自己画点小数据手玩一下.

代码

#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <cctype>
#include <cstdio>
#include <cstring>

typedef long long LL;
const int N = 200050;
int pre[N], nxt[N], fr[N], to[N], a[N], cnt;
bool rm[N];

int read() {
  int ans = 0, c;
  while (!isdigit(c = getchar()));
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans;
}

typedef std::pair<int, int> E;
#define mp std::make_pair

std::priority_queue<E> Q;
int fa[N];

int main() {
  int n = read(), m = read(), q = read();
  for (int i = 1; i <= m; ++i) {
    int x = fr[i] = read();
    to[i] = read();
    nxt[i] = pre[x];
    pre[x] = i;
    a[i] = q + 1;
  }
  for (int i = 0; i < q; ++i) {
    int x = read();
    if (a[x] > i) rm[a[x] = i] = true;
    else rm[i] = false;
  }
  to[m + 1] = 1;
  Q.push(mp(0, m + 1));
  while (!Q.empty()) {
    E x = Q.top(); Q.pop();
    int u = x.second, t = to[u];
    if (fa[t]) continue;
    fa[t] = u;
    for (int i = pre[t]; i; i = nxt[i])
      Q.push(mp(a[i], i));
  }
  for (int i = n; i != 1; i = fr[fa[i]]) {
    // printf("%d %d %d\n", i, fa[i], a[fa[i]]);
    rm[a[fa[i]]] = false;
  }
  for (int i = 0; i < q; ++i)
    printf("%d\n", rm[i] ? 1 : 0);
}

一些吐槽

我不是很懂出题人为什么把这题放到月赛第三题, 我觉得得出这个贪心并证明它并不是困难的. 更不懂为什么出题人没有在题解上给出更简单的做法. 大约是其真的没想到吧.

更奇怪的是居然比赛时少有人 AC. 是不是放在 C 题就把大家吓跑了, 想到贪心也觉得是假的呢?