BZOJ4242 水壶题解

题意：

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

IOI 市是一个被分成纵 \(H\) \(\times\) 横 \(W\) 块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有 \(P\) 个，编号为 \(1,2,\cdots ,P\)。

cxy 只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。

cxy 因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上的日光十分强烈，因此在原野上每走过一个区域都需要 \(1\) 单位的水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此 IOI 市的市民一般都携带水壶出行。大小为 \(x\) 的水壶最多可以装 \(x\) 单位的水，建筑物里有自来水可以将水壶装满。

由于携带大水壶是一件很困难的事情，因此 cxy 决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。

现在给出 IOI 市的地图和 \(Q\) 个询问，第 \(i\) 个询问 \((1\le i\le Q)\) 为 “在建筑物 \(S_i\) 和 \(T_i\) 之间移动，最小需要多大的水壶？”，请你对于每个询问输出对应的答案。

如果我们把 \(n\) 个建筑物当做 \(n\) 个结点

不难发现这个答案就是最小生成树中 \(S_i\) 与 \(T_i\) 的路径中最大边的权值。

注意到这是一张平面图，显然有 \(|E| \le 3|V| - 6\) 。

那么问题就转化了树上路径最大值询问，采用倍增。

时间复杂度 \(\mathcal{O}(Q \log n)\) ，这题有点卡常。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace __fastio
{
    const int bufl=1<<20;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a)
        {a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        template<typename Temp>inline void getDouble(Temp &a)
        {a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();
        if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
        IN& operator>>(char &a){a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        # ifndef int
        IN& operator>>(long long &a){getInt(a);return *this;}
        # endif
        IN& operator>>(__int128 &a){getInt(a);return *this;}
        IN& operator>>(float &a){getDouble(a);return *this;}
        IN& operator>>(double &a){getDouble(a);return *this;}
        # ifndef double
        IN& operator>>(long double &a){getDouble(a);return *this;}
        # endif
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a)
        {if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a)
        {if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putInt(b);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        # ifndef int
        OUT& operator<<(long long a){putInt(a);return *this;}
        # endif
        OUT& operator<<(__int128 a){putInt(a);return *this;}
        OUT& operator<<(float a){putDouble(a);return *this;}
        OUT& operator<<(double a){putDouble(a);return *this;}
        # ifndef double
        OUT& operator<<(long double a){putDouble(a);return *this;}
        # endif
        ~OUT(){flush();}
    };
}using __fastio::IN;using __fastio::OUT; IN fin; OUT fout;
#define N ((int)(2e3+15))
#define mxV ((int)(3e5+15))
#define mxE ((int)(4e6+15))
#define ID(x) (id[x.r][x.c])
#define F(x) (f[x.r][x.c])

const int dr[4] = {1,-1,0,0};
const int dc[4] = {0,0,1,-1};

char mp[N][N];
int R,C,V,Q,E,pos=1,head[mxV << 1];
int lg2[mxV],dep[mxV],fa[mxV],sz[mxV];
int f[N][N],id[N][N],P[mxV][19],D[mxV][19];

struct node{ int r,c; } a[mxV];
struct Edge{ int u,v,w,next; } e0[mxE << 1],e[mxV << 1];

queue<node> q;
bool operator<(Edge a,Edge b) { return a.w < b.w; }

void init(int n) { for(int i=1; i<=n; i++) fa[i] = i, sz[i] = 1; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

bool merge(int u,int v)
{
    int x = find(u), y = find(v);
    if(x == y) return 0;
    if(sz[x] < sz[y]) swap(x,y);
    fa[x] = y; sz[y] += sz[x];
    return 1;
}
void addEdge0(int u,int v,int w)
{
    // cout << "u = " << u << ',' << " v = " << v << '\n';
    if(E && e0[E-1].u == u && e0[E-1].v == v) return;
    e0[++E] = {u,v,w}; e0[++E] = {v,u,w};
}
void addEdge(int u,int v,int w)
{
    e[++pos] = {u,v,w,head[u]}; head[u] = pos;
    e[++pos] = {v,u,w,head[v]}; head[v] = pos;
}
void bfs()
{
    node p1,p2;
    for(int i=1; i<=V; i++) { q.push(a[i]); ID(a[i]) = i; }
    // for(int i=1; i<=V; i++) cout << ID(a[i]) << ' '; cout << '\n';
    while(!q.empty())
    {
        p1 = q.front(); q.pop();
        // cout << p1.r << ' ' << p1.c << '\n';
        for(int k=0; k<4; k++)
        {
            p2 = {p1.r + dr[k], p1.c + dc[k]};
            if(mp[p2.r][p2.c] != '.') continue;
            if(!ID(p2))
            {
                ID(p2) = ID(p1); F(p2) = F(p1) + 1; q.push(p2);
                // cout << p2.r << ' ' << p2.c << '\n';
            }else if(ID(p1) < ID(p2))
                { addEdge0(ID(p1), ID(p2), F(p1) + F(p2)); }
        }
    }
}
void kruskal()
{
    init(V); sort(e0+1,e0+E+1);
    for(int i=1,cnt=0; i<=E && cnt < V-1; i++)
    {
        int u=e0[i].u, v=e0[i].v, w=e0[i].w;
        if(merge(u,v))
        { ++cnt; addEdge(u,v,w); }
    }
}
void dfs(int u)
{
    for(int i=0; i<18 && P[u][i]; i++)
    {
        P[u][i+1] = P[P[u][i]][i];
        D[u][i+1] = max(D[u][i], D[P[u][i]][i]);
    }
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; 
        if(v == P[u][0]) continue;
        P[v][0] = u; D[v][0] = e[i].w;
        dep[v] = dep[u] + 1; dfs(v);
    }
}
int query(int x,int y)
{
    if(find(x) != find(y)) return -1;
    int res = 0;
    if(dep[x] < dep[y]) swap(x, y);
    for(int k; dep[x] > dep[y]; ) 
    {
        k=lg2[dep[x] - dep[y]] - 1;
        up(res, D[x][k]); x = P[x][k]; 
    }
    if(x == y) return res;
    for(int k=18; ~k; k--)
        if(P[x][k] != P[y][k])
        {
            up(res, D[x][k]); x = P[x][k];
            up(res, D[y][k]); y = P[y][k];
        }
    up(res, D[x][0]); up(res, D[y][0]);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    fin >> R >> C >> V >> Q;
    for(int i=1; i<=R; i++) fin >> (mp[i]+1);
    for(int i=1; i<=V; i++) fin >> a[i].r >> a[i].c;
    lg2[1] = 0 + 1;
    for(int i=2; i<=V; i++) lg2[i] = lg2[i >> 1] + 1;
    bfs(); kruskal();
    for(int i=1; i<=V; i++) if(!dep[i]) { dep[i] = 1; dfs(i); }
    for(int u,v; Q--; ) { fin >> u >> v; fout << query(u,v) << '\n'; }
    return 0;
}