题解：P6543 [CEOI2014] 007

· · 题解

洛谷 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，但我们可以模拟一下这样的策略会产生的问题：

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

那么何时答案需要减一呢？仔细思考，可以发现问题一定出在 从 \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));
    }
}