「题解」「BZOJ4456」 旅行者

oi

「BZOJ4456」 旅行者


妈耶,这道题的难度。
两个小时吧…题解大大帮了不少的忙。
我第一次跑的时候第一个点17s…
顺着题解的各种思路优化优化,然后才优化到了这份代码。
为啥没人解释SPFA那段该怎么优化啊!那里明明是性能瓶颈。
这道题要好好解释一下,太神了。

首先解释这道题的核心…分治方法。
一开始看的我一脸懵逼,这道题咋做。
后来一看标签,分治啊分治…
然后kd-tree的思路就该上了。
我们每一次对一个矩形进行划分,用最长的一个边对半分,然后对分成两半的矩形里的点进行讨论,
对于做全在左右半边的点,我们先不考虑,我们考虑跨越左右矩形的点。
对于每个点点距离,我们进行以下计算:枚举划分点到点点的距离,然后类floyd跑出最短距离。
然后递归对剩下的矩形进行处理。

但是…这道题的细节很蛋疼。
有两个难度较大的细节,如何保证每次计算的都是在矩形内的查询。
细节2,怎么优化SPFA。
嗯…明天写(咕咕咕)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// by kririae
#define inf 0x3f3f3f3f
#define R register
#define ll long long
#define pii pair<int, int>
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
inline char gc()
{
static char buf[1 << 18], *fs, *ft;
return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read()
{
register int k = 0, f = 1;
register char c = gc();
for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
return k * f;
}
}

namespace BZOJ4456
{
const int maxn = 2e5 + 5, maxq = 1e5 + 5;

struct Edge
{
int to, val;
Edge(int t, int v) : to(t), val(v) {}
};
vector<Edge> edges[maxn];
struct Query
{
int x, y, id;
} q[maxq], tmp[maxq];
int n, m, val, Q, dis[maxn], res[maxq];
pii idx[maxn];
bitset<maxn> vis;
queue<int> qwq;

inline void addedge(int from, int to, int val)
{
edges[from].push_back(Edge(to, val));
edges[to].push_back(Edge(from, val));
}

inline int calc(int x, int y)
{
return (x - 1) * m + y;
}

inline void SPFA(int xs, int ys, int xl, int xr, int yl, int yr, bool flag)
{
// 一个骚优化
int d = dis[calc(xs, ys)];
for (R int i = xl; i <= xr; ++i)
for (R int j = yl; j <= yr; ++j)
dis[calc(i, j)] = flag ? dis[calc(i, j)] + d : inf;
int s = calc(xs, ys);
dis[s] = 0, vis[s] = 1, qwq.push(s);
while(!qwq.empty())
{
int curr = qwq.front(); qwq.pop(); vis[curr] = 0;
for (int i = 0; i < edges[curr].size(); ++i)
{
Edge &e = edges[curr][i];
int tox = idx[e.to].first, toy = idx[e.to].second;
if(tox >= xl && tox <= xr && toy >= yl && toy <= yr)
if(dis[e.to] > dis[curr] + e.val)
{
dis[e.to] = dis[curr] + e.val;
if(!vis[calc(tox, toy)]) qwq.push(calc(tox, toy)), vis[calc(tox, toy)] = 1;
}
}
}
}

inline void solve(int xl, int xr, int yl, int yr, int l, int r)
{
if(l > r) return;
if(xr - xl <= yr - yl)
{
int mid = (yl + yr) >> 1;
for (R int i = xl; i <= xr; ++i)
{
SPFA(i, mid, xl, xr, yl, yr, i != xl);
for (R int j = l; j <= r; ++j)
res[q[j].id] = min(res[q[j].id], dis[q[j].x] + dis[q[j].y]);
}
int tl = l - 1, tr = r + 1;
for (R int i = l; i <= r; ++i)
{
int y1 = idx[q[i].x].second, y2 = idx[q[i].y].second;
if(y1 < mid && y2 < mid) tmp[++tl] = q[i];
else if(y1 > mid && y2 > mid) tmp[--tr] = q[i];
}
for (R int i = l; i <= tl; ++i) q[i] = tmp[i];
for (R int i = tr; i <= r; ++i) q[i] = tmp[i];
solve(xl, xr, yl, mid - 1, l, tl);
solve(xl, xr, mid + 1, yr, tr, r);
} else {
int mid = (xl + xr) >> 1;
for (R int i = yl; i <= yr; ++i)
{
SPFA(mid, i, xl, xr, yl, yr, i != yl);
for (R int j = l; j <= r; ++j)
res[q[j].id] = min(res[q[j].id], dis[q[j].x] + dis[q[j].y]);
}
int tl = l - 1, tr = r + 1;
for (R int i = l; i <= r; ++i)
{
int x1 = idx[q[i].x].first, x2 = idx[q[i].y].first;
if(x1 < mid && x2 < mid) tmp[++tl] = q[i];
else if(x1 > mid && x2 > mid) tmp[--tr] = q[i];
}
for (R int i = l; i <= tl; ++i) q[i] = tmp[i];
for (R int i = tr; i <= r; ++i) q[i] = tmp[i];
solve(xl, mid - 1, yl, yr, l, tl);
solve(mid + 1, xr, yl, yr, tr, r);
}
}

inline void solve()
{
memset(dis, 0x3f, sizeof(dis));
memset(res, 0x3f, sizeof(res));
using namespace IO;
n = read(), m = read();
for (R int i = 1; i <= n; ++i)
for (R int j = 1; j <= m; ++j)
idx[calc(i, j)] = make_pair(i, j);
for (R int i = 1; i <= n; ++i)
for (R int j = 1; j < m; ++j)
addedge(calc(i, j), calc(i, j + 1), read());
for (R int i = 1; i < n; ++i)
for (R int j = 1; j <= m; ++j)
addedge(calc(i, j), calc(i + 1, j), read());
Q = read();
for (R int i = 1; i <= Q; ++i)
{
int a = read(), b = read(), c = read(), d = read();
q[i].x = calc(a, b), q[i].y = calc(c, d), q[i].id = i;
}
solve(1, n, 1, m, 1, Q);
for (R int i = 1; i <= Q; ++i)
printf("%d\n", res[i]);
}
}

int main()
{
return BZOJ4456::solve(), 0;
}