bzoj 4456 [Zjoi2016]旅行者

题面

https://www.lydsy.com/JudgeOnline/problem.php?id=4456

题解

分治

设当前work的区间为(x1,y1,x2,y2)

我们将长边分成两半

不妨设长边是(x1,x2)

那么令mid=(x1+x2)/2

对于分界线(mid,y1)~(mid,y2)的所有点我们做最短路

得到分界线上所有点到区间里任意点的最短路

那么对于询问(sx,sy,tx,ty) 我们可以枚举分界线上某一点(mid,y) 并且用dist((mid,y),(sx,sy))+dist((mid,y),(tx,ty))更新答案

然后对于(sx,sy)和(tx,ty)都落在分界线同一侧的询问我们递归求解

这样做的正确性：每一组询问，一定会经过某次的分界线，在计算到这条分界线的时候就可以算到答案

复杂度：T(n)=4T(n/2)+O(n*(m+nlogm)) m为边数也就是n^2

那么T(n)=n^3（这是n约等于m的情况）可以通过这道题

n和m差距大的时候更快

Code

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 
  5 ll read(){
  6     ll x=0,f=1;char c=getchar();
  7     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
  8     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
  9     return x*f;
 10 }
 11 
 12 const int maxn=100100;
 13 int n,m,q;
 14 int a[150][maxn],b[150][maxn];
 15 bool vis[150][maxn];
 16 bool flag;
 17 int res[100100];
 18 
 19 struct P{
 20     int x;
 21     pair<int,int> y;
 22     bool operator <(const P &a) const{
 23         return x>a.x;
 24     }
 25 };
 26 
 27 priority_queue<P> pq;
 28 
 29 struct query{
 30     int a,b,c,d;
 31     int p,ans;
 32     void input(){
 33         a=read(),b=read(),c=read(),d=read();
 34     }
 35 } que[100100];
 36 
 37 int dis[150][maxn];
 38 int num[150][maxn];
 39 
 40 void update(int nwx,int nwy,int nwdis){
 41     //cout<<nwx<<' '<<nwy<<' '<<nwdis<<endl;
 42     if(dis[nwx][nwy]>nwdis){
 43         dis[nwx][nwy]=nwdis;
 44         pq.push(P{nwdis,make_pair(nwx,nwy)});
 45     }
 46 }
 47 void doit(int x,int y,int X1,int Y1,int X2,int Y2){
 48     //cout<<X1<<' '<<Y1<<' '<<X2<<' '<<Y2<<' '<<x<<' '<<y<<endl;
 49     for(int i=X1;i<=X2;i++)
 50         for(int j=Y1;j<=Y2;j++)
 51             dis[i][j]=1e9,vis[i][j]=0;
 52     dis[x][y]=0;
 53     pq.push(P{0,make_pair(x,y)});
 54     while(!pq.empty()){
 55         P nw=pq.top();
 56         pq.pop();
 57         int X=nw.y.first,Y=nw.y.second;
 58         //cout<<X<<' '<<Y<<' '<<dis[X][Y]<<endl;
 59         if(vis[X][Y]) continue;
 60         vis[X][Y]=1;int dist=dis[X][Y];
 61         if(X>X1) update(X-1,Y,dist+b[X-1][Y]);
 62         if(X<X2) update(X+1,Y,dist+b[X][Y]);
 63         if(Y>Y1) update(X,Y-1,dist+a[X][Y-1]);
 64         if(Y<Y2) update(X,Y+1,dist+a[X][Y]);
 65     }
 66 }
 67 
 68 void solve(int nwa,int nwb,int nwc,int nwd,int l,int r){
 69     //cout<<nwa<<' '<<nwb<<' '<<nwc<<' '<<nwd<<endl;
 70     if(l>r) return;
 71     int len1=nwc-nwa+1,len2=nwd-nwb+1;
 72     if(len1>=len2){
 73         int md=(nwa+nwc)>>1;
 74         for(int j=nwb;j<=nwd;j++){
 75             doit(md,j,nwa,nwb,nwc,nwd);
 76             for(int k=l;k<=r;k++){
 77                 //cout<<que[k].p<<' '<<dis[que[k].a][que[k].b]<<' '<<dis[que[k].c][que[k].d]<<endl;
 78                 que[k].ans=min(que[k].ans,dis[que[k].a][que[k].b]+dis[que[k].c][que[k].d]);
 79             }
 80         }
 81         if(nwa<md){
 82             int pos=l-1;
 83             for(int i=l;i<=r;i++){
 84                 if(que[i].a<md && que[i].c<md) pos++,swap(que[i],que[pos]);
 85             }
 86             solve(nwa,nwb,md-1,nwd,l,pos);
 87         }
 88         if(md<nwc){
 89             int pos=l-1;
 90             for(int i=l;i<=r;i++){
 91                 if(que[i].a>md && que[i].c>md) pos++,swap(que[i],que[pos]);
 92             }
 93             solve(md+1,nwb,nwc,nwd,l,pos);
 94         }
 95     }
 96     else{
 97         int md=(nwb+nwd)>>1;
 98         for(int i=nwa;i<=nwc;i++){
 99             doit(i,md,nwa,nwb,nwc,nwd);
100             for(int k=l;k<=r;k++){
101                 //cout<<que[k].p<<' '<<dis[que[k].a][que[k].b]<<' '<<dis[que[k].c][que[k].d]<<endl;                
102                 que[k].ans=min(que[k].ans,dis[que[k].a][que[k].b]+dis[que[k].c][que[k].d]);
103             }
104         }
105         if(nwb<md){
106             int pos=l-1;
107             for(int i=l;i<=r;i++){
108                 if(que[i].b<md && que[i].d<md) pos++,swap(que[i],que[pos]);
109             }
110             solve(nwa,nwb,nwc,md-1,l,pos);
111         }
112         if(md<nwd){
113             int pos=l-1;
114             for(int i=l;i<=r;i++){
115                 if(que[i].b>md && que[i].d>md) pos++,swap(que[i],que[pos]);
116             }
117             solve(nwa,md+1,nwc,nwd,l,pos);
118         }
119     }
120 }
121 
122 int main(){
123 #ifdef LZT
124     freopen("in","r",stdin);
125     freopen("out","w",stdout);
126 #endif
127     n=read();m=read();
128     if(n>m) flag=1;
129     for(int i=1;i<=n;i++){
130         for(int j=1;j<m;j++){
131             if(!flag) a[i][j]=read();
132             else b[j][i]=read();
133         }
134     }
135     for(int i=1;i<n;i++){
136         for(int j=1;j<=m;j++){
137             if(!flag) b[i][j]=read();
138             else a[j][i]=read();
139         }
140     }
141     q=read();
142     for(int i=1;i<=q;i++){
143         que[i].input();
144         if(flag) swap(que[i].a,que[i].b),swap(que[i].c,que[i].d);
145         que[i].p=i;que[i].ans=2e9;
146     }
147     if(flag) swap(n,m);
148     
149     solve(1,1,n,m,1,q);
150 
151     for(int i=1;i<=q;i++)
152         res[que[i].p]=que[i].ans;
153     for(int i=1;i<=q;i++)
154         printf("%d
",res[i]);
155     return 0;
156 }
157 
158 /*
159 2 2
160 2
161 3
162 6 4
163 2
164 1 1 2 2
165 1 2 2 1
166 */

View Code

Review

分治还是比较明显的

然而数据的处理十分麻烦

因为条件是n×m的范围

所以我们得同时考虑n=m和n>>m的情况

代码中的处理方法是跟别人学的很棒棒要多写几遍