咕了2天才写的题解

还是比较经典的题目，分治处理网格图最短路

离线下来，利用分治的思想，用一条线把网格图平均劈成两半，每次只考虑询问在两块的一对点，所有的线必须经过直线上的一个点，于是我把线上所有点都在规定范围内跑一次dijkstra，最后直接算答案，显然我想让最短路跑的次数最小，每次选较短的边作为线段的长度，从较高的边上劈开，如果一组询问在同一块，分别递归，就是子问题了。这个做法正确性显然。

时间复杂度证明如下：

设点数有
\(|V|\)
个，当前分治在第
\(k\)
轮，那么线的长度就最多是
\(\sqrt{\frac{|V|}{2^k}}\)
，要进行线的长度次的dijkstra，因为网格图点数与边数同级，所以每次dijkstra时间复杂度是
\(O(\frac{|V|}{2^k}\log\frac{|V|}{2^k})\)
，即
\(O(\frac{|V|}{2^k}\log{|V|})\)
，然后第
\(k\)
轮，要分治
\(2^k\)
次，时间复杂度是
\(O(2^k\cdot\sqrt{\frac{|V|}{2^k}}\frac{|V|}{2^k}\log{|V|})\)
，整理得
\(\frac{|V|^{\frac{3}{2}}\cdot \log{|V|}}{2^{\frac{k}{2}}}\)
，有
\(k\)
轮，分母相加，由等比数列求和公式，知道是个常数，如果我没算错的话就是
\(\sqrt{2}+1\)
，然后时间复杂度就是
\(O(|V|^{\frac{3}{2}}\cdot \log{|V|})\)
，这道题
\(|V|\)
最大是2e4，这么算下来最多也只有4e7级别

#include<bits/stdc++.h>
#define vd void 
#define MAXN 200005 
#define pr std::pair<int,int>
#define fi first
#define se second 
const int inf=1e9;
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
template<class T>vd cnk(T&a,T b){a=a<=b?a:b;}
struct Q{
	int pos,st,ed;
}query[MAXN],g[MAXN],g2[MAXN];
int n,m,q,ans[MAXN],x[MAXN],y[MAXN],dis[MAXN];
bool vis[MAXN];
std::vector<pr>nbr[MAXN];
struct node{
	int to,W;
	bool friend operator<(node a,node b){return a.W>b.W;}
};
std::priority_queue<node>pq;
int id(int xx,int yy){return (xx-1)*m+yy;}
vd add(int xx,int yy,int w){nbr[xx].emplace_back(yy,w),nbr[yy].emplace_back(xx,w);}
vd dijkstra(int s,int xl,int xr,int yl,int yr){
	for(int i=xl;i<=xr;i++)for(int j=yl;j<=yr;j++)dis[id(i,j)]=inf,vis[id(i,j)]=0;
	dis[s]=0;pq.push({s,0});
	while(!pq.empty()){
		int u=pq.top().to;pq.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(pr v:nbr[u]){
			if(x[v.fi]<xl||x[v.fi]>xr||y[v.fi]<yl||y[v.fi]>yr)continue;
			if(dis[v.fi]>dis[u]+v.se)dis[v.fi]=dis[u]+v.se,pq.push({v.fi,dis[v.fi]});
		}
	}
}
vd solve(int ql,int qr,int xl,int xr,int yl,int yr){
	if(ql>qr||xl>xr||yl>yr)return;
	if(xr-xl>=yr-yl){
		int mid=(xl+xr)>>1,lg=0,lg2=0;
		for(int i=yl;i<=yr;i++){
			dijkstra(id(mid,i),xl,xr,yl,yr);
			for(int j=ql;j<=qr;j++)cnk(ans[query[j].pos],dis[query[j].st]+dis[query[j].ed]);
		}
		for(int i=ql;i<=qr;i++){
			if(x[query[i].st]<mid&&x[query[i].ed]<mid)g[++lg]=query[i];
			else if(x[query[i].st]>mid&&x[query[i].ed]>mid)g2[++lg2]=query[i];
		}
		for(int i=1;i<=lg;i++)query[ql+i-1]=g[i];
		for(int i=1;i<=lg2;i++)query[ql+lg+i-1]=g2[i];
		solve(ql,ql+lg-1,xl,mid-1,yl,yr),solve(ql+lg,ql+lg+lg2-1,mid+1,xr,yl,yr);
	}else{
		int mid=(yl+yr)>>1,lg=0,lg2=0;
		for(int i=xl;i<=xr;i++){
			dijkstra(id(i,mid),xl,xr,yl,yr);
			for(int j=ql;j<=qr;j++)cnk(ans[query[j].pos],dis[query[j].st]+dis[query[j].ed]);
		}
		for(int i=ql;i<=qr;i++){
			if(y[query[i].st]<mid&&y[query[i].ed]<mid)g[++lg]=query[i];
			else if(y[query[i].st]>mid&&y[query[i].ed]>mid)g2[++lg2]=query[i];
		}
		for(int i=1;i<=lg;i++)query[ql+i-1]=g[i];
		for(int i=1;i<=lg2;i++)query[ql+lg+i-1]=g2[i];
		solve(ql,ql+lg-1,xl,xr,yl,mid-1),solve(ql+lg,ql+lg+lg2-1,xl,xr,mid+1,yr);
	}
}
int main(){
	n=gi(),m=gi();
	for(int i=1;i<=n;i++)for(int j=1;j<m;j++){int w=gi();add(id(i,j),id(i,j+1),w);};
	for(int i=1;i<n;i++)for(int j=1;j<=m;j++){int w=gi();add(id(i,j),id(i+1,j),w);};
	q=gi();
	for(int i=1;i<=q;i++){
		int a=gi(),b=gi(),c=gi(),d=gi();
		query[i]={i,id(a,b),id(c,d)},ans[i]=inf;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)x[id(i,j)]=i,y[id(i,j)]=j;
	solve(1,q,1,n,1,m);
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
}

算是一个套路吧，网格图最短路想分治

标签: none

添加新评论