月赛题 P8860 题解

· · 题解

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

题意

有一张 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} 的大小.

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

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 题就把大家吓跑了, 想到贪心也觉得是假的呢?