自动搬运

查看原文

来自洛谷，原作者为

	Mr_罗 π⁴+π⁵≈e⁶ | Per Aspera Ad Astra | トゲナシトゲアリ > MyGO!!!!!

搬运于2025-08-24 22:21:45，当前版本为作者最后更新于2024-10-14 20:45:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

洛谷 P6543 [CEOI2014] 007 & LOJ #3289. 「CEOI2014」007。

upd on 2024/10/15 13:12:40：修改一处笔误。 upd on 2024/10/15 14:39:45：修改亿处笔误。

题意

在无向无权图上有警、匪和相邻的两处机密，每回合匪先走，警后走，可以不走，匪目标为走到某处机密并花一回合获得，警目标是在匪获得机密前某一回合走到匪当时所在的点，求警最多可以摆烂几回合（摆烂时无法抓匪）。

数据范围：点数 $n\le 2\times 10^5$，边数 $m\le 6\times 10^5$。

题解

先后走无关紧要，看作同时走，即警最晚需要在匪到机密时走到匪的位置。

首先容易发现警可以在机密处「守株待小粉兔」，因此警一定走最短路，所以匪也一定走最短路。那么容易判掉 $-1$ 的情况：对于某一个机密，警一定比匪晚到。

设 $ds_i$ 表示以警为起点的最短路，$dt_i$ 表示以匪为起点的最短路，则警摆烂的上限显然是 $\min\{dt_a-ds_a,dt_b-ds_b\}$。

那么这是不是最终答案呢？稍加思考便可以举出反例：有可能匪「虚晃」了一下警，把警骗到歧路中后抄近道，这时答案需要减一。例如下面这张图：

P.S. 略微不对称，强迫症体谅一下 :)

P.P.S 如果 $\it{d=8}$ 那么也无解，相当于 $\it{0-1=-1}$。

在这个例子里，$s=1,d=9,a=4,b=5$。本来上限是 $\min\{3-2,3-2\}=1$，但我们可以模拟一下这样的策略会产生的问题：

• 第一回合：匪走到 $8$；警摆烂。
• 第二回合：匪走到 $6$；警走到 $2$。
• 第三回合：匪走到 $5$；警走到 $4$。
• 第四回合：匪获胜。

这样警就必须提前一回合出发，答案需要减一。

那么何时答案需要减一呢？仔细思考，可以发现问题一定出在 从 $\boldsymbol{s,d}$ 到 $\boldsymbol{a,b}$ 的最短路的分叉点 上：倘若 警在匪还可以走两条最短路重合部分时，自己便必须抉择需要先照顾 $\boldsymbol{a}$ 还是 $\boldsymbol{b}$，那么匪就可以把警「晃飞」，这样答案就必须减一。即设 $s'$ 为 $s$ 到 $a,b$ 的最短路最长能重合的位置，$d'$ 为 $d$ 的最长位置，那么当且仅当 $ds_{s'}+\min\{dt_a-ds_a,dt_b-ds_b\}<dt_{d'}$ 时答案需要减一。

当然这样做有前提条件，就是 $dt_a-ds_a=dt_b-ds_b$，否则警就直接走等待时间更短的那条路就好了，不用管匪。

剩下的代码就很好写了，判掉无解，找到上限，找到最长重合位置（$ds/dt$ 最大的位置且在 $s/t\to a,b$ 最短路上），判断即可。

constexpr int N = 200005;
constexpr ll mod = 998244353;
int n, m, s, t, x, y, k;
vector<int> G[N];
int ds[4][N];
int qu[N], lh, rt;

#define d ds[t]
void bfs(int s, int t) {
    qu[lh = rt = 1] = s, d[s] = 0; while (lh <= rt) {
        int u = qu[lh++];
        for (auto v : G[u]) if (d[v] < 0) d[v] = d[u] + 1, qu[++rt] = v;
    }
}

void solve() {
    scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &x, &y); rep(i, 1, m) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v), G[v].emplace_back(u);
    } mem(ds, -1), bfs(s, 0), bfs(t, 1);
    if (int d1 = ds[1][x] - ds[0][x], d2 = ds[1][y] - ds[0][y]; (k = min(d1, d2)) < 0) { puts("-1"); return; }
    else if (d1 != d2) printf("%d\n", k);
    else {
        int p = 0, q = 0; bfs(x, 2), bfs(y, 3);
        rep(i, 1, n) if (ds[2][i] == ds[3][i]) {
            if (ds[0][i] + ds[2][i] == ds[0][x]) chkmx(p, ds[0][i]);
            if (ds[1][i] + ds[3][i] == ds[1][y]) chkmx(q, ds[1][i]);
        }
        printf("%d\n", k - (p + k < q));
    }
}