Studying Father's luogu blog

Focus on interest!

题解 P3645 【[APIO2015]雅加达的摩天楼】

一种建模方法(直接连边)

对于每个 doge 所在点,我们直接从出发点向其可达点连边,边权为需要跳的步数。

在建成的图上直接跑最短路即可。

这种情况下,图上的边规模最大可能达到 $O(n^2)$(本文默认 $n,m$ 同阶)。

另一种建模方法(分层图)

我们发现直接连边过程中,边可以拆分。

例如 $u \to p \to v$ 这条路径,我们连了 $u \to p$,$u \to v$ 两条边,事实上我们可以连 $u \to p$,$p \to v$ 这两条边,达到同样的目的。

但是直接在原图上连边会出问题。原因在于我们到某个中间点的时候,并不一定能就地更换 doge。

考虑建立分层图。对于每个 doge 建立 $n$ 个点,这 $n$ 个点之间按上文的方式连边,同时这 $n$ 个点可以向原图相对应的点,连一条边权为 $0$ 的单向边(表示可以更换 doge),从原图中 doge 所在的出发位置向其所在的层中的对应点,连一条边权为 $0$ 的单向边(意义同上)。

事实上这种建模方式,在最坏情况下连边的数量仍然为 $O(n^2)$。

满分做法

联想到根号分治,我们想到一种利用分块思想,结合上面两种建图方式,实现优化的方法:设置一个分界点 $k$,对于 $p \leq k$ 的 doge,采用分层图方式建图,而对于 $p \geq k$ 的 doge,则采用直接连边的方式建图。

问题在于这个分界点 $k$ 该取到多少?

我们可以证明,当 $k=\sqrt{\dfrac{n}{3}}$ 时,图上的边数达到最少。

下面是证明:

  • 对于采用分层图建图的部分,每个层的点需要连三条边(一条向左,一条向右,还有一条连向原图上的相应点),因为一共有 $k$ 层,故最多需要 $3kn$ 条边。
  • 对于直接连边建图的部分,每个点最多需要对外连 $\dfrac{n}{k}$ 条边,故最多有 $\dfrac{n^2}{k}$ 条边。
  • 即总边数为 $3kn+\dfrac{n^2}{k}$ 条边。
  • 由均值不等式可知,当 $3kn=\dfrac{n^2}{k}$,即 $k=\sqrt{\dfrac{n}{3}}$ 时,图上的边数达到最小值 $2n\sqrt{3n}$。

细节

  1. 把图建出来需要的内存空间较大(虽然注意实现细节的话,并不会超过内存限制),可以考虑不显式连边,而是在转移的时候进行讨论。
  2. 总点数和边数较大,注意常数。
// Problem: P3645 [APIO2015] 雅加达的摩天楼
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3645
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
struct edge {
  int v, w, next;
} e[18000005];
int head[3100005], id[105][30005], dis[3100005], cnt;
bool vis[3100005];
int n, m;
void addedge(int u, int v, int w) {
  e[++cnt].v = v;
  e[cnt].w = w;
  e[cnt].next = head[u];
  head[u] = cnt;
}
int dijkstra(int s, int t) {
  priority_queue<pii, vector<pii>, greater<pii> > pq;
  memset(dis, INF, sizeof(dis));
  dis[s] = 0;
  pq.push(make_pair(0, s));
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (dis[v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        pq.push(make_pair(dis[v], v));
      }
    }
  }
  return dis[t] != INF ? dis[t] : -1;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  int maxp = sqrt(n / 3);
  int s, t;
  for (int i = 1; i <= maxp; i++)
    for (int j = 0; j < n; j++) id[i][j] = i * n + j;
  for (int i = 1; i <= maxp; i++)
    for (int j = 0; j < n; j++) {
      addedge(id[i][j], j, 0);
      if (i + j >= n) break;
      addedge(id[i][j], id[i][j + i], 1);
      addedge(id[i][j + i], id[i][j], 1);
    }
  for (int i = 0; i < m; i++) {
    int b, p;
    cin >> b >> p;
    if (p <= maxp)
      addedge(b, id[p][b], 0);
    else {
      for (int j = 1; b + j * p < n; j++) addedge(b, b + j * p, j);
      for (int j = 1; b - j * p >= 0; j++) addedge(b, b - j * p, j);
    }
    if (i == 0) s = b;
    if (i == 1) t = b;
  }
  for (int i = 1; i <= maxp; i++)
    for (int j = 0; j < n; j++)
      if (head[id[i][j]]) addedge(id[i][j], j, 0);
  cout << dijkstra(s, t) << endl;
  return 0;
}

2020-08-02 20:46:43 in 题解