题解：P3350 [ZJOI2016] 旅行者
my_dream666
·
·
题解
前言
题目传送门。
前置知识：分治，最短路。
解决方法
看到矩形和多次询问，直接采取分治。
将当前矩形按较长的边分成两份。这时每个查询可以分成几种情况。
-
该查询必须经过分界线。
-
该查询没有经过边界线。
- 该查询最短路经过边界线。
- 该查询最短路没有经过边界线，那么递归到左/右解决。
根据上面的分类讨论，可以知道我们只需要求出边界线上的每个点到当前矩形的每个点的最短路。
:::warning[注意]
求最短路要用 dijkstra，不要用 spfa，因为网格图可以轻松卡 spfa，稍不注意就会被卡。
:::
这也就是我们要按长边来分治的原因。
同样会将矩形分成两份，但是跑 dijkstra 的点数会降低很多。
分析时间是复杂度是这题的一个难点，我们直接采用主定理。
主定理
主定理非常适合用于递归算法的时间复杂度的分析。
对于每一层的时间复杂度的形式如下,f(n) 是本层（第一层）的时间复杂度：
T(n)=aT(n/b)+f(n)\quad a\geq 1,b>1
那么它的总时间复杂度是：
T(n)=
\begin{cases}
n^{\log_ba} &n^{\log_ba}>f(n)\\
n^{\log_ba}\log n &n^{\log_ba}=f(n)\\
f(n) &n^{\log_ba}<f(n)
\end{cases}
:::warning[注意]{open}
这里的 = 指相同，>,< 指多项式意义上的大于小于，即必须至少相差一个 n^{\epsilon}。
举个例子，如果 f(n)=n\log n,n^{\log_ba}=n，他们两就不是同级也不是大于小于的关系。
也就是说那个式子无法用现在我们这个主定理来求。
所以要用第四种情况了。
T=
n^{\log_ba}\log^{k+1}n \quad f(n)=n^{\log_ba}\log^kn
可以发现，上面的第 2 种情况也可以归属到第 4 中情况。
综上所述，主定理的完备形式是：
T(n)=
\begin{cases}
n^{\log_ba} &f(n)<n^{\log_ba}\\
n^{\log_ba}\log n &f(n)=n^{\log_ba}\\
f(n) &f(n)>n^{\log_ba}\\
n^{\log_ba}\log^{k+1}n &f(n)=n^{\log_ba}\log^kn
\end{cases}
或
T(n)=
\begin{cases}
n^{\log_ba} &f(n)<n^{\log_ba}\\
f(n) &f(n)>n^{\log_ba}\\
n^{\log_ba}\log^{k+1}n &f(n)=n^{\log_ba}\log^kn
\end{cases}
主定理当然有局限性，存在上面情况都不符合的式子，举个例子：$n^{\log_ba}=n,f(n)=n\log\log n$。
:::
证明我就懒得证了。
### 时间复杂度
每一层最坏的情况都是正方形，即短边长为 $\sqrt S$。
则
$$
\begin{aligned}
f(S)&=\sqrt S\times S\log S=S^{3/2}\log S\\
T(S)&=2T(S/2)+f(S)\\
\because f(S)&>S^{\log_ba}=S\\
\therefore T(S)&=f(S)=\sqrt S\times S\log S
\end{aligned}
$$
因此计算的时间复杂度为 $\mathcal O(\sqrt S\times S\log S)$。
再算查询时间复杂度，每个点最坏都到最后一层，那么计算出所有可能遍历的分界点个数就行了。
$$
\begin{aligned}
f(S)&=\sqrt S=S^{1/2}\\
T(S)&=T(S/2)+f(S)\\
\because f(S)&>S^{\log_ba}=1\\
\therefore T(S)&=f(S)=\sqrt S
\end{aligned}
$$
所以查询时间复杂度为 $\mathcal O(Q\sqrt S)$。
总的时间复杂度为 $\mathcal O(\sqrt S\times S\log S+Q\sqrt S),S=n\times m$。
:::info[code]
```cpp
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<cstring>
#include<algorithm>
# define inf 0x3f3f3f3f
# define pipii pair <int,pair<int,int>>
# define F first
# define S second
using namespace std;
const int N=2e4+10;
const int M=1e5+10;
struct question
{
int ans;
int x1,x2,y1,y2;
}Q[M];
int n,m,l1,r1,l2,r2;
vector <int> c;
vector <vector<int>> dis,a,b;
priority_queue <pipii,vector<pipii>,greater<pipii>> q;
void read()
{
return ;
}
template <typename T,typename ...Args>
void read(T &x,Args &...args)
{
x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
read(args...);
}
bool safe(int x1,int y1)
{
return (x1>=l1&&y1>=r1&&x1<=l2&&y1<=r2);
}
void dij(int x,int y)
{
for(int i=l1;i<=l2;i++)
for(int j=r1;j<=r2;j++) dis[i][j]=inf;
dis[x][y]=0;
q.push({0,{x,y}});
pipii now;
int xx,yy;
while(!q.empty())
{
now=q.top(); q.pop();
if(now.F!=dis[now.S.F][now.S.S]) continue;
xx=now.S.F; yy=now.S.S+1;
if(safe(xx,yy))
{
if(dis[xx][yy]>now.F+a[now.S.F][now.S.S])
{
dis[xx][yy]=now.F+a[now.S.F][now.S.S];
q.push({dis[xx][yy],{xx,yy}});
}
}
xx=now.S.F+1; yy=now.S.S;
if(safe(xx,yy))
{
if(dis[xx][yy]>now.F+b[now.S.F][now.S.S])
{
dis[xx][yy]=now.F+b[now.S.F][now.S.S];
q.push({dis[xx][yy],{xx,yy}});
}
}
xx=now.S.F; yy=now.S.S-1;
if(safe(xx,yy))
{
if(dis[xx][yy]>now.F+a[xx][yy])
{
dis[xx][yy]=now.F+a[xx][yy];
q.push({dis[xx][yy],{xx,yy}});
}
}
xx=now.S.F-1; yy=now.S.S;
if(safe(xx,yy))
{
if(dis[xx][yy]>now.F+b[xx][yy])
{
dis[xx][yy]=now.F+b[xx][yy];
q.push({dis[xx][yy],{xx,yy}});
}
}
}
}
void solve(int x1,int y1,int x2,int y2,vector <int> &f)
{
if(x1==x2&&y1==y2)
{
for(int i=0;i<f.size();i++) Q[f[i]].ans=0;
return ;
}
l1=x1; r1=y1; l2=x2; r2=y2;
int mid;
vector <int> L,R;
if(x2-x1>y2-y1)
{
mid=(x1+x2)>>1;
for(int i=y1;i<=y2;i++)
{
dij(mid,i);
for(int i=0;i<f.size();i++) Q[f[i]].ans=min(Q[f[i]].ans,dis[Q[f[i]].x1][Q[f[i]].y1]+dis[Q[f[i]].x2][Q[f[i]].y2]);
}
for(int i=0;i<f.size();i++)
{
if(Q[f[i]].x1<mid&&Q[f[i]].x2<mid) L.push_back(f[i]);
else if(Q[f[i]].x1>mid&&Q[f[i]].x2>mid) R.push_back(f[i]);
}
if(L.size()&&x1<=mid-1) solve(x1,y1,mid-1,y2,L);
if(R.size()&&mid+1<=x2) solve(mid+1,y1,x2,y2,R);
}
else
{
mid=(y1+y2)>>1;
for(int i=x1;i<=x2;i++)
{
dij(i,mid);
for(int i=0;i<f.size();i++) Q[f[i]].ans=min(Q[f[i]].ans,dis[Q[f[i]].x1][Q[f[i]].y1]+dis[Q[f[i]].x2][Q[f[i]].y2]);
}
for(int i=0;i<f.size();i++)
{
if(Q[f[i]].y1<mid&&Q[f[i]].y2<mid) L.push_back(f[i]);
else if(Q[f[i]].y1>mid&&Q[f[i]].y2>mid) R.push_back(f[i]);
}
if(L.size()&&y1<=mid-1) solve(x1,y1,x2,mid-1,L);
if(R.size()&&mid+1<=y2) solve(x1,mid+1,x2,y2,R);
}
}
int main()
{
int qu;
read(n,m);
dis=vector<vector<int>>(n+10,vector<int>(m+10));
a=vector<vector<int>>(n+10,vector<int>(m+10));
b=vector<vector<int>>(n+10,vector<int>(m+10));
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++) read(a[i][j]);
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++) read(b[i][j]);
read(qu);
for(int i=1;i<=qu;i++) read(Q[i].x1,Q[i].y1,Q[i].x2,Q[i].y2),Q[i].ans=inf;
for(int i=1;i<=qu;i++) c.push_back(i);
solve(1,1,n,m,c);
for(int i=1;i<=qu;i++) printf("%d\n",Q[i].ans);
return 0;
}
```
:::
## 后记
通过这道题，我学到了分治求多次询问的网格图最短路的求法，以及主定理。
非常感谢。