题解：P14422 [JOISC 2014] 水桶 / Water Bottle

心灵震荡 · 2025-12-02 17:42:29 · 题解

把原图中每两个点连上边，边权为这两个点之间的距离。不难发现一组询问 (s, t) 的答案就是这个图的 MST 上 s, t 两点路径上的最大值，也是 kruscal 重构树上这两点 LCA 的点权。

由于边的数量是 O(p^2) 级别的，肯定会超时。

考虑多源 bfs，从每个城市开始 bfs 的过程中，如果以两个城市起始的路径在某块地交了，那我们就连上边。正确性显然，考虑对于一条边，若它没有在 bfs 过程中被连上，那它的边权一定更大，也就不优。

查询就是重构树上跳 LCA。

#include <bits/stdc++.h>
using namespace std;

const int N = 2005, M = 4e5 + 5;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int n, m, p, q, fa[M], siz[N], dis[N][N], a[M], b[M];
int dif[N][N], tot, cr[M], f[M][22], dep[M], x, y;
char s[N][N];
queue<int> qx, qy, qt;
vector<int> g[M];

inline int find(int x)
{
    return (x == fa[x] ? x : fa[x] = find(fa[x]));
}

void merge(int x, int y)
{
    fa[x] = y;
}

struct edge
{
    int u, v, w;

    bool operator < (const edge &nd) const
    {
        return w < nd.w;
    }
} e[M * 10];

int eds;

void bfs()
{
    while(!qx.empty())
    {
        int x = qx.front(), y = qy.front(), w = qt.front();
        qx.pop(), qy.pop(), qt.pop();
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m || s[nx][ny] == '#') continue;
            if(dif[nx][ny])
            {
                if(w != dif[nx][ny])
                    e[++eds] = {dif[nx][ny], w, dis[x][y] + dis[nx][ny]};
            }
            else
            {
                dis[nx][ny] = dis[x][y] + 1, dif[nx][ny] = w;
                qx.push(nx), qy.push(ny), qt.push(w);
            }
        }
    }
    return;
}

void dfs(int u, int fa)
{
    f[u][0] = fa, dep[u] = dep[fa] + 1;
    for(int i = 1; i <= 20; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for(auto v : g[u]) dfs(v, u);
    return;
}

inline int LCA(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 20; i >= 0; i--)
        if(dep[f[x][i]] >= dep[y]) x = f[x][i];
    if(x == y) return x;
    for(int i = 20; i >= 0; i--)
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> p >> q; tot = p;
    for(int i = 1; i <= n; i++)
        cin >> (s[i] + 1);
    for(int i = 1; i <= 2 * p; i++) fa[i] = i;
    for(int i = 1; i <= p; i++)
    {
        cin >> a[i] >> b[i];
        qx.push(a[i]), qy.push(b[i]), qt.push(i);
        dis[a[i]][b[i]] = 0;
        dif[a[i]][b[i]] = i;
    }
    bfs();
    sort(e + 1, e + eds + 1);
    for(int i = 1; i <= eds; i++)
    {
        x = find(e[i].u), y = find(e[i].v);
        if(x == y) continue;
        cr[++tot] = e[i].w;
        g[tot].push_back(x);
        g[tot].push_back(y);
        fa[x] = tot, fa[y] = tot;
    }
    for(int i = 1; i <= tot; i++)
        if(i == find(i)) dfs(i, 0);
    while(q--)
    {
        cin >> x >> y;
        if(find(x) != find(y)) cout << -1 << '\n';
        else cout << cr[LCA(x, y)] << '\n';
    }
    return 0;
}