题解 P3645 【[APIO2015]雅加达的摩天楼】
StudyingFather
2020-08-02 20:46:43
## 一种建模方法（直接连边）
对于每个 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. 总点数和边数较大，注意常数。
```cpp
// 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;
}
```