JOISC2014 水筒

题目:

  JOI 君所居住的 IOI 市以一年四季都十分炎热著称。

  IOI 市被分成 行,每行包含 块区域。每个区域都是建筑物、原野、墙壁之一。
  IOI 市有 个区域是建筑物,坐标分别为
  JOI 君只能进入建筑物与原野,而且每次只能走到相邻的区域中,且不能移动到市外。

  JOI 君因为各种各样的事情,必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好,但原野上太阳非常毒辣,因此在原野上每走过一个区域都需要 1 升水。此外,原野上没有诸如自动售货机、饮水处之类的东西,因此 IOI 市的市民一般都携带水壶出行。大小为 的水壶最多可以装 升水,建筑物里有自来水可以将水壶装满。
  由于携带大水壶是一件很困难的事情,因此 JOI 君决定携带尽量小的水壶移动。因此,为了随时能在建筑物之间移动,请你帮他写一个程序来计算最少需要多大的水壶。

  现在给出 IOI 市的地图和 个询问,第 个询问包含两个整数 ,对于每个询问,请输出:要从建筑物 移动到 ,至少需要多大的水壶?

思路:

  先考虑 的暴力(怎么暴力只有这么点啊qwq),可以通过广搜建出一个有 条边的图。要求图上两点间路径,使得路径上的最大值最小。显然这样的答案是在整个图的最小生成树上,那么只要在最小生成树上倍增,就能做到 查询了。
  现在整个题目的复杂度都卡在建树上。事实上,建树时不需要每个点都为起点进行一次广搜。一开始把所有的建筑扔进队列,然后记录每个点是以哪个建筑为起点遍历到的,经过的距离。每次遍历到一个被遍历过的点,就说明这两个起点的中会有一条长度为两点距离和的边(只有这些边可能出现在最小生成树中)。再用这些边建最小生成树即可(其实可以在广搜的过程中建树,但是同一层的点有一些细节比较麻烦)。这样的边最多有 个。所以复杂度是可以接受的。

代码:

#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int M=2005,N=2e5+5;

bool cur1;

#define erep(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator[] (int x){return W[x];}
};
struct Edge{int to,w;};
Link<N,N<<1,Edge> G;

const int fx[]={0,1,0,-1},fy[]={1,0,-1,0};
int n,m,p,q;
char mp[M][M];
int px[N],py[N];

int ufs[N];
int find(int x){
    return ufs[x]==x?x:ufs[x]=find(ufs[x]);
}

void readChar(char &c){
    do c=getchar();
    while(c!='.'&&c!='#');
}

struct Point{
    int x,y;
};
struct EdgeBfs{
    int u,v,w;
    bool operator < (const EdgeBfs _) const {
        return w<_.w;
    }
};
std::vector<EdgeBfs> edge;
int mark[M][M],dis[M][M];
bool end[N];
void build(){
    std::queue<Point> q;
    rep(i,1,p){
        ufs[i]=i;
        q.push((Point){px[i],py[i]});
        mark[px[i]][py[i]]=i;
    }
    while(!q.empty()){
        Point p=q.front();q.pop();
        rep(k,0,3){
            int tx=p.x+fx[k],ty=p.y+fy[k];
            if(mp[tx][ty]!='.')continue;
            if(mark[tx][ty]){
                int x=mark[tx][ty],y=mark[p.x][p.y];
                edge.push_back((EdgeBfs){x,y,dis[tx][ty]+dis[p.x][p.y]});
            }
            else {
                mark[tx][ty]=mark[p.x][p.y];
                dis[tx][ty]=dis[p.x][p.y]+1;
                q.push((Point){tx,ty});
            }
        }
    }
    std::sort(edge.begin(),edge.end());
    for(EdgeBfs e:edge){
        if(find(e.u)==find(e.v))continue;
        G.add(e.u,(Edge){e.v,e.w});
        G.add(e.v,(Edge){e.u,e.w});
//      printf("(%d,%d)=%d\n",e.u,e.v,e.w);
        ufs[find(e.u)]=find(e.v);
    }
}

int st[N][20],fa[N][20],dep[N];
bool vis[N];
void dfs(int o,int f){
    vis[o]=true;
    dep[o]=dep[f]+1;
    erep(k,G,o){
        int v=G[k].to;
        if(v==f)continue;
        fa[v][0]=o;st[v][0]=G[k].w;
        dfs(v,o);
    }
}
int qry(int u,int v){
    if(find(u)!=find(v))return -1;
    if(dep[u]>dep[v])std::swap(u,v);
    int d=dep[v]-dep[u];
    int ans=0;
    rep(i,0,17)
        if(d>>i&1){
            tomax(ans,st[v][i]);
            v=fa[v][i];
        }
    if(u==v)return ans;
    drep(i,17,0){
        if(fa[u][i]==fa[v][i])continue;
        tomax(ans,st[u][i]);tomax(ans,st[v][i]);
        u=fa[u][i];v=fa[v][i];
    }
    tomax(ans,st[u][0]);tomax(ans,st[v][0]);
    return ans;
}

bool cur2;

int main(){
//  printf("%lf\n",(&cur2-&cur1)/1024.0/1024);
    scanf("%d%d%d%d",&n,&m,&p,&q);
    rep(i,1,n)
        rep(j,1,m)
            readChar(mp[i][j]);
    rep(i,1,p)scanf("%d%d",px+i,py+i);
    build();
    rep(i,1,p)
        if(!vis[i])
            dfs(i,0);
    rep(k,1,17)
        rep(i,1,p){
            st[i][k]=std::max(st[i][k-1],st[fa[i][k-1]][k-1]);
            fa[i][k]=fa[fa[i][k-1]][k-1];
        }
    rep(i,1,q){
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",qry(u,v));
    }
    return 0;
}