LOJ

分析

这题有很多种讲法...

  1. 「AMPPZ2014」Petrol 放到网格图上。
  2. 求出离每个格子最近的建筑,然后对于每对相邻的最近建筑不相同的原野,在它们的最近建筑间连一条边权为距离的边,然后就变成了「NOIP2013」货车运输。
  3. 求出离每个格子最近的建筑,然后对于每对相邻的最近建筑不相同的原野,在它们的最近建筑间连一条边权为距离的边,然后建出 Kruskal 重构树,每次询问 LCA 的点权就是答案。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,L=2000+10;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int H,W,P,Q;
char a[L][L];
struct node { int x,y; } c[N];

int cnt=0;
struct edge { int u,v,w; } e[4*L*L];
bool operator <(edge a,edge b) { return a.w<b.w; }

int dis[L][L],nr[L][L];
inline void bfs() {
    memset(dis,0x3f,sizeof(dis)); queue<node> Q;
    for (re int i=1;i<=P;++i) {
        nr[c[i].x][c[i].y]=i,dis[c[i].x][c[i].y]=0;
        Q.push(c[i]);
    }
    while (!Q.empty()) {
        int x=Q.front().x,y=Q.front().y; Q.pop();
        for (re int d=0;d<4;++d) {
            int X=x+dx[d],Y=y+dy[d];
            if (X<1||X>H||Y<1||Y>W||a[X][Y]=='#') continue;
            if (nr[X][Y]) continue;
            nr[X][Y]=nr[x][y],dis[X][Y]=dis[x][y]+1;
            Q.push((node){X,Y});
        }
    }
}
inline void build() {
    for (re int x=1;x<=H;++x)
        for (re int y=1;y<=W;++y) {
            if (a[x][y]=='#') continue;
            for (re int d=0;d<2;++d) {
                int X=x+dx[d],Y=y+dy[d];
                if (X>H||Y>W||a[X][Y]=='#') continue;
                if (nr[x][y]!=nr[X][Y])
                    e[++cnt]=(edge){nr[x][y],nr[X][Y],dis[x][y]+dis[X][Y]};
            }
        }
}

int rt[N<<1];
inline int find(int x) { return x==rt[x]?x:rt[x]=find(rt[x]); }

vector<int> E[N<<1];
int w[N<<1],dep[N<<1],f[19][N<<1];
inline void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,f[0][u]=fa;
    for (re int i=1;i<19;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int v:E[u]) dfs(v,u);
}
inline int getlca(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=18;~i;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (dep[u]!=dep[v]) u=f[0][u];
    for (re int i=18;~i;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    if (u!=v) u=f[0][u];
    return u;
}
inline void kruskal() {
    sort(e+1,e+cnt+1); int tot=P;
    for (re int i=1;i<=P<<1;++i) rt[i]=i;
    for (re int i=1;i<=cnt;++i) {
        int u=find(e[i].u),v=find(e[i].v);
        if (u!=v) { ++tot;
            E[tot].push_back(u),rt[u]=tot;
            E[tot].push_back(v),rt[v]=tot;
            w[tot]=e[i].w;
        }
    }
    for (re int i=1;i<=tot;++i) if (!dep[i]) dfs(find(i),0);
}

int main() {
    H=read(),W=read(),P=read(),Q=read();
    for (re int i=1;i<=H;++i) scanf("%s",a[i]+1);
    for (re int i=1;i<=P;++i) c[i].x=read(),c[i].y=read();
    bfs(); build(); kruskal();
    while (Q--) {
        int u=read(),v=read();
        if (find(u)!=find(v)) puts("-1");
        else printf("%d\n",w[getlca(u,v)]);
    }
    return 0;
}
最后修改:2019 年 10 月 28 日 03 : 24 PM