A simple Blog for wyx I've been down the bottle hoping.
4456: [Zjoi2016]旅行者 最短路 分治 卡常数
发表于: | 分类: Oi | 评论:0 | 阅读:173

这是一道非常不错的题目……我们可以利用分治+最短路来解决这个问题

具体的方法是每次定位出一个矩形表示处理这个矩形的询问,然后每次把这个矩形分成相等的两部分,分的依据是每次把长的边劈成两半,然后考虑枚举这条线上的每一个点跑最短路,然后更新一下所有询问,显然这时两个点如果不在一个块内答案已经统计完了,现在只需要考虑在一个块内的,那么处理子问题即可。

容易发现每次面积变小一半,那么边长的变化就是$\sqrt{n}$级别的

那么复杂度就是$n\sqrt{n}\log{n}$

这些都不是重点

我要说的是这题卡常数,卡常……数,常……数,数……数

我从20分卡到50,然后卡到80最后卡到97

$extra\ test\ 5$实在是太强了,根本卡不过Orz,看旁边的$Infinity37$顺利A掉本人表示一脸懵逼

如果你看到这些字说明图片GG了

#include <queue>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define in(x,a,b) ((x)>=(a)&&(x)<=(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 4e4+5;
const int M = N << 1;
const int inf = 0x7fffffff;

  
inline char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
  
inline int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}
  
int n, m;

vector <int> id[N];

struct graph {
    graph *next; int to,val;
}edge[M], *head[N], *C = edge;

inline void add(int x,int y,int z) {
    C ++; C -> to = y; C -> val = z; C -> next = head[x]; head[x] = C;
    C ++; C -> to = x; C -> val = z; C -> next = head[y]; head[y] = C;
}
/*
inline void add(int x,int y,int z) {
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z); head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z); head[y] = cnt;
}
*/
namespace Heap
{
    int h[N<<1],tot;
    int pos[N<<1];
    inline void up(int x)
    {
        if(x==1)
            return;
        while(h[x]<h[x>>1])
        {
            if(x==1)break;
            swap(h[x],h[x>>1]);
            swap(pos[x],pos[x>>1]);
            x>>=1;
        }
    }
    inline void push(int x,int y)
    {
        h[++tot]=x;
        pos[tot]=y;
        up(tot);
    }
    inline int pop()
    {
        swap(h[1],h[tot]);
        swap(pos[1],pos[tot--]);
        int i=1;
        while((((i<<1)<=tot)&&(h[i]>h[i<<1]))||(((i<<1)+1<=tot)&&(h[i]>h[(i<<1)+1])))
        {
            if((i<<1)+1>tot)
            {
                swap(h[i],h[i<<1]);
                swap(pos[i],pos[i<<1]);
                i<<=1;
            }
            else
            {
                int tmp=(h[i<<1]<h[(i<<1)+1])?(i<<1):((i<<1)+1);
                swap(h[i],h[tmp]);
                swap(pos[i],pos[tmp]);
                i=tmp;
            }               
        }
        return pos[tot+1];    
    }
    inline bool empty()
    {
        return tot == 0;
    }
}

using namespace Heap;

int dis[N], X[N], Y[N];
bool vis[N];

inline void dij (int s,int x1,int x2,int y1,int y2) {
    register int i,j;
    for(i=x1;i<=x2;++i)
        for(j=y1;j<=y2;++j) 
            dis[id[i][j]] = inf;
    for(i=x1;i<=x2;++i)
        for(j=y1;j<=y2;++j)
            vis[id[i][j]] = false;
    push(0,s); dis[s] = 0;
    static graph *p;
    static int To;
    while(!empty()) {
        int tt = pop();
        if(vis[tt]) continue;
        vis[tt] = 1;
        for(p=head[tt];p;p=p->next) {
            if(in(X[(To = p->to)],x1,x2) && in(Y[To],y1,y2)) {
                if(dis[To] > dis[tt] + p->val && !vis[To]) {
                    dis[To] = dis[tt] + p->val;
                    push(dis[To],To);
                }
            }
        }
    }
}

int ans[N*10];

struct data {
    int x0,y0,x1,y1, u, v, id;
}ask[N*10], tmp[N*10];

int i,j;

inline void solve(int x1,int x2,int y1,int y2,int L,int R) {
    if(L > R) return;
    bool flag = false;
    int l, r;
    if(x2 - x1 < y2 - y1) l = y1, r = y2, flag = 1;
    else l = x1, r = x2, flag = 0;
    int mid = (l+r) >> 1;
    if(flag) {
        for(i=x1;i<=x2;++i) {
            dij(id[i][mid],x1,x2,y1,y2);
            for(j=L;j<=R;++j) {
                ans[ask[j].id] = min(ans[ask[j].id], dis[ask[j].u] + dis[ask[j].v]);
            }
        }
    }
    else {
        for(i=y1;i<=y2;++i) {
            dij(id[mid][i],x1,x2,y1,y2);
            for(j=L;j<=R;++j) {
                ans[ask[j].id] = min(ans[ask[j].id], dis[ask[j].u] + dis[ask[j].v]);
            }
        }
    }
    int tmpl = L - 1, tmpr = R + 1;
    for(i=L;i<=R;++i)  {
        if(flag) {
            if(ask[i].y0 < mid && ask[i].y1 < mid) tmp[++tmpl] = ask[i];
            else if(ask[i].y0 > mid && ask[i].y1 > mid) tmp[--tmpr] = ask[i];
        } 
        else {
            if(ask[i].x0 < mid && ask[i].x1 < mid) tmp[++tmpl] = ask[i];
            else if(ask[i].x0 > mid && ask[i].x1 > mid) tmp[--tmpr] = ask[i];
        }
    }
    for(i=L;i<=tmpl;++i) ask[i] = tmp[i];
    for(i=tmpr;i<=R;++i) ask[i] = tmp[i];
    if(flag) solve(x1,x2,y1,mid-1,L,tmpl), solve(x1,x2,mid+1,y2,tmpr,R);
    else solve(x1,mid-1,y1,y2,L,tmpl), solve(mid+1,x2,y1,y2,tmpr,R);
}

int main() {
    n = read(), m = read();
    for(i=1;i<=n;++i) id[i].pb(0);
    int cnt = 0;    
    for(i=1;i<=n;++i) {
        for(j=1;j<=m;++j) {
            id[i].pb(++cnt);
            X[cnt] = i, Y[cnt] = j;
        }
    }
    for(i=1;i<=n;++i) {
        for(j=1;j<m;++j) {
            add(id[i][j],id[i][j+1],read());
        }
    }
    for(i=1;i<n;++i)
        for(j=1;j<=m;++j) {
            add(id[i][j],id[i+1][j],read());
        }
    int  T = read();
    for(i=1;i<=T;++i) {
        ask[i].id = i;
        ask[i].x0 = read(), ask[i].y0 = read(), ask[i].x1 = read(), ask[i].y1 = read();
        ask[i].u = id[ask[i].x0][ask[i].y0];  ask[i].v = id[ask[i].x1][ask[i].y1];
        if(ask[i].u == ask[i].v) ans[i] = 0;
        else ans[i] = inf;
    }
//  puts("yes");
    solve(1,n,1,m,1,T);
    for(i=1;i<=T;++i) printf("%d\n", ans[i]);
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP