LOJ #2876. 「JOISC 2014 Day2」水壶 题解

Description

JOI 君所居住的 IOI 市以一年四季都十分炎热著称。

IOI 市被分成 $H$ 行，每行包含 $W$ 块区域。每个区域都是建筑物、原野、墙壁之一。
IOI 市有 $P$ 个区域是建筑物，坐标分别为 $(A_1, B_1),$ $(A_2, B_2),$ $\ldots,$ $(A_P, B_P)$。
JOI 君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。

JOI 君因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上太阳非常毒辣，因此在原野上每走过一个区域都需要 1 升水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此 IOI 市的市民一般都携带水壶出行。大小为 $x$ 的水壶最多可以装 $x$ 升水，建筑物里有自来水可以将水壶装满。
由于携带大水壶是一件很困难的事情，因此 JOI 君决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。

现在给出 IOI 市的地图和 $Q$ 个询问，第 $i$ 个询问包含两个整数 $S_i,$ $T_i$，对于每个询问，请输出：要从建筑物 $S_i$ 移动到 $T_i$，至少需要多大的水壶？

数据范围：$H,W\leq2000$，$P,Q\leq2\times10^5$，$1\leq S_i,T_i\leq P$。

Solution

首先对于任意两个建筑物连一条边权为他们的距离的边，那么对于每个询问，显然就是求最小瓶颈生成树两点间的最大权值。

考虑如何建出这个最小生成树。

可以先 bfs 求出距离每个原野最近的建筑物，那么对于每个建筑物，他管辖的原野一定是个连通块，考虑对于连通块有相邻边的两个建筑物连边，然后跑 kruskal 最小生成树。

感性理解一下，这样做显然能够连出一个生成树，并且对于每个点都保存了离他最近的几条边，所以这样做肯定能求出最小生成树。

时间复杂度：$O\left(HW+(P+Q)\log P\right)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxH = 2e3 + 5, kMaxP = 2e5 + 5, kMaxE = 4e6 + 5;
const int kDx[] = {0, 0, 1, -1}, kDy[] = {1, -1, 0, 0};

int h, w, p, q;
int a[kMaxP], b[kMaxP], fa[kMaxP][19], faw[kMaxP][19], dep[kMaxP], lg[kMaxP];
std::vector<std::pair<int, int>> G[kMaxP];
std::vector<std::tuple<int, int, int>> ed;
std::string s[kMaxH];

struct DSU {
  std::vector<int> fa;

  void init(int _n) { fa.resize(_n + 1), std::iota(fa.begin(), fa.end(), 0); }
  
  DSU() {}
  DSU(int _n) { init(_n); }

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

  void unionn(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
  }
} dsu;

void bfs() {
  static int dis[kMaxH][kMaxH], idx[kMaxH][kMaxH];
  for (int i = 1; i <= h; ++i) {
    for (int j = 1; j <= w; ++j) {
      dis[i][j] = idx[i][j] = -1;
    }
  }
  std::queue<std::tuple<int, int, int>> q;
  for (int i = 1; i <= p; ++i) {
    dis[a[i]][b[i]] = 0, idx[a[i]][b[i]] = i;
    q.emplace(a[i], b[i], i);
  }
  for (; !q.empty();) {
    auto [x, y, id] = q.front();
    q.pop();
    for (int k = 0; k < 4; ++k) {
      int tx = x + kDx[k], ty = y + kDy[k];
      if (tx < 1 || tx > h || ty < 1 || ty > w || s[tx][ty] == '#') continue;
      if (!~idx[tx][ty]) {
        dis[tx][ty] = dis[x][y] + 1, idx[tx][ty] = id;
        q.emplace(tx, ty, id);
      } else if (idx[tx][ty] != id) {
        ed.emplace_back(dis[x][y] + dis[tx][ty], id, idx[tx][ty]);
      }
    }
  }
}

void kruskal() {
  dsu.init(p);
  std::sort(ed.begin(), ed.end());
  for (auto [w, u, v] : ed) {
    if (dsu.find(u) != dsu.find(v)) {
      dsu.unionn(u, v), G[u].emplace_back(v, w), G[v].emplace_back(u, w);
    }
  }
}

void dfs(int u, int fa) {
  ::fa[u][0] = fa, dep[u] = dep[fa] + 1;
  for (int i = 1; i <= lg[p]; ++i) {
    ::fa[u][i] = ::fa[::fa[u][i - 1]][i - 1];
    faw[u][i] = std::max(faw[u][i - 1], faw[::fa[u][i - 1]][i - 1]);
  }
  for (auto [v, w] : G[u]) {
    if (v == fa) continue;
    faw[v][0] = w;
    dfs(v, u);
  }
}

void lca_prework() {
  lg[0] = -1;
  for (int i = 1; i <= p; ++i)
    lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= p; ++i) {
    if (!dep[i]) {
      dfs(i, 0);
    }
  }
}

int getans(int x, int y, int id = 0) {
  if (dep[x] < dep[y]) std::swap(x, y);
  int ret = 0;
  for (int i = lg[p]; ~i; --i)
    if (dep[fa[x][i]] >= dep[y])
      ret = std::max(ret, faw[x][i]), x = fa[x][i];
  if (x == y) return ret;
  for (int i = lg[p]; ~i; --i) {
    if (fa[x][i] != fa[y][i]) {
      ret = std::max({ret, faw[x][i], faw[y][i]});
      x = fa[x][i], y = fa[y][i];
    }
  }
  return std::max({ret, faw[x][0], faw[y][0]});
}

void dickdreamer() {
  std::cin >> h >> w >> p >> q;
  for (int i = 1; i <= h; ++i) {
    std::cin >> s[i];
    s[i] = " " + s[i];
  }
  for (int i = 1; i <= p; ++i)
    std::cin >> a[i] >> b[i];
  bfs(), kruskal(), lca_prework();
  for (int i = 1; i <= q; ++i) {
    int s, t;
    std::cin >> s >> t;
    std::cout << (dsu.find(s) == dsu.find(t) ? getans(s, t, i) : -1) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}