CERC2016 机棚障碍

对于每个点,求出以它为中心的最大正方形边长,然后问题就转变为在一个权值在点上的图中求一个点到另外一个点中经过点权最小值最大的一条路径。这个过程可以将所有障碍点压入队列跑 BFS,往八个方向拓展,最短路径即为最大正方形边长。

看到这个,应该可以想到 Kruskal 重构树,但是权值在点上该怎么处理?因为一条边被经过的话两端点就被经过,所以边权等于两端点点权较小值。

剩下的就是 Kruskal 重构树基本操作。

这道题考场差点就切了 就没想到点权怎么转边权 草

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

const int MAXN = 2e3;
const int NXT[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

int n, m, edge, tot, cnt; 
int wt[MAXN | 1][MAXN | 1], id[MAXN | 1][MAXN | 1];
int wk[MAXN * MAXN << 1 | 1], firstE[MAXN * MAXN << 1 | 1], depth[MAXN * MAXN << 1 | 1], topf[MAXN * MAXN << 1 | 1], father[MAXN * MAXN << 1 | 1], fset[MAXN * MAXN << 1 | 1], size[MAXN * MAXN << 1 | 1], son[MAXN * MAXN << 1 | 1];
char g[MAXN | 1][MAXN | 2];

struct Queue {
  int x, y, step;
  Queue() {}
  Queue(int a, int b, int c) : x(a), y(b), step(c) {}
} q[MAXN * MAXN | 1];

struct EE {
  int from, to, w;
  EE() {}
  EE(int a, int b, int c) : to(b), from(a), w(c) {}
  friend bool operator < (const EE &lhs, const EE &rhs) {
    return lhs.w > rhs.w;
  }
} p[MAXN * MAXN << 1 | 1];

struct Edge {
  int to, nxt;
  Edge() {}
  Edge(int a, int b) : to(b), nxt(firstE[a]) {}
} e[MAXN * MAXN << 1 | 1];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

inline void addEdge(int a, int b) {
  e[++edge] = Edge(a, b);
  firstE[a] = edge;
}

void getWt() {
  int head = 1, tail = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (g[i][j] == '#') {
        q[++tail] = Queue(i, j, 0);
      }
    }
  }
  do {
    Queue from = q[head++];
    for (int i = 0; i < 8; ++i) {
      int tx = from.x + NXT[i][0], ty = from.y + NXT[i][1];
      if (tx < 1 || tx > n || ty < 1 || ty > n || wt[tx][ty] || g[tx][ty] == '#') continue;
      q[++tail] = (Queue(tx, ty, from.step + 1));
      wt[tx][ty] = std::min(tx, std::min(n - tx + 1, std::min(ty, std::min(n - ty + 1, from.step + 1)))) * 2 - 1;
    }
  } while(head <= tail);
}

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

void Kruskal() {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 0; k < 4; ++k) {
        int tx = i + NXT[k][0], ty = j + NXT[k][1];
        if (tx < 1 || tx > n || ty < 1 || ty > n) continue;
        if (std::min(wt[i][j], wt[tx][ty]) != 0) {
          p[++cnt] = EE(id[i][j], id[tx][ty], std::min(wt[i][j], wt[tx][ty]));
        }
      }
    }
  }
  std::sort(p + 1, p + 1 + cnt);
  for (int i = 1; i <= n * n * 2; ++i) fset[i] = i;
  int count = 0;
  tot = n * n;
  for (int i = 1; i <= cnt; ++i) {
    int x = find(p[i].from), y = find(p[i].to), z = p[i].w;
    if (x == y) continue;
    ++count;
    wk[++tot] = z;
    fset[x] = fset[y] = tot;
    addEdge(tot, x);
    addEdge(tot, y);
    if (count == n * n - 1) break;
  }
}

void dfs1(int x, int fa) {
  size[x] = 1;
  father[x] = fa;
  depth[x] = depth[father[x]] + 1;
  for (int k = firstE[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == fa) continue;
    dfs1(to, x);
    size[x] += size[to];
    if (size[to] > size[son[x]]) son[x] = to;
  }
}

void dfs2(int x, int ftop) {
  topf[x] = ftop;
  if (son[x]) dfs2(son[x], ftop);
  for (int k = firstE[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if (to == father[x] || to == son[x]) continue;
    dfs2(to, to);
  }
}

int LCA(int x, int y) {
  if (find(x) != find(y)) return 0;
  while (topf[x] != topf[y]) {
    if (depth[topf[x]] < depth[topf[y]]) std::swap(x, y);
    x = father[topf[x]];
  }
  return depth[x] < depth[y] ? x : y;
}

int query(int a, int b, int c, int d) {
  int lca = LCA(id[a][b], id[c][d]);
  return wk[lca];
}

int main() {
  n = read();
  for (int i = 1; i <= n; ++i)
    scanf("%s", g[i] + 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      id[i][j] = (i - 1) * n + j;
    }
  }
  getWt();
  Kruskal();
  for (int i = tot; i >= 1; --i) {
    if (!size[i]) {
      dfs1(i, 0);
      dfs2(i, i);
    }
  }
  m = read();
  while (m--) {
    int a = read(), b = read(), c = read(), d = read();
    printf("%d\n", query(a, b, c, d));
  }
  return 0;
}
最后修改:2019 年 08 月 16 日 11 : 09 AM

发表评论