题解：P14422 [JOISC 2014] 水桶 / Water Bottle

· · 题解

闲话

又被大手子拉过来写题的一天。

正文

题面有点过长了，简化一下。

形式化题意

在 H\times W 的二维平面上，存在障碍和 P 个点。

定义边权：两点之间的最短路径大小。

一共有 Q 次查询，每次给出两个点，问你两点是否可达。如果可达，请输出两点所经过路径的最大边权的最小值（路径可以是直接的，也可以是经过其他点“绕路”过来的）；否则输出 -1。

暴力

直接每次都跑一遍搜索，但是明显时间是 \Theta(Q\times H\times W) 的，直接炸缸。

正解

发现这个题本质是让我们求图上最小瓶颈路。（不会的看这里）。

你可以这么想：

查询结果是最大边权最小值，那我们要是让边权最小，我们就考虑每次找最小的边，如果这条边可以被替换，就没必要选，否则就选上，直到查询的两点联通（不联通输出 -1）。

然后你做完了这些，你就发现自己“发明”了克鲁斯卡尔，那我们为什么不直接上最小生成树，然后去跑最小瓶颈路呢？

好了，思路上的问题解决了，但是我怎么得到一个图呢？我总不能每个点跑一遍广搜吧？

的确，所以我们考虑只跑一遍广搜，只要加一点点优化。我们在把所有起点塞进队列里，然后染色扩展，当我们发现有一个点的颜色不是空白也不是自己的颜色，说明有起点已经到过了这里，那我们把两个起点之间建一条边，边权为距离减一（题目要求），之后不在这个点扩展。

这样可以保证图上每个点只会被染色一次，遍历不超过两次，而且建出的边只会是两点之间的最短路径长度，数量一定不会很多，就算你悲观估计，边数也不会超过 \Theta(H\times W) 的量级。

跑出图后就是最小瓶颈路板子了，我这里用了树链剖分，时间是 \Theta(H\times W+H\times W\times \log _2(H\times W)+Q \times \log _2P)，分别是多源广搜，克鲁斯卡尔和树剖查询的时间。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
int xx[4]={-1,0,1,0},yy[4]={0,1,0,-1};
using T=array<int,3>;
using P=array<int,2>;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int h,w,p,q;cin>>h>>w>>p>>q;
    V<V<int> >mp(h+1,V<int>(w+1,INF));
    V<V<int> >dis(h+1,V<int>(w+1,INF));
    V<T>edge;V<V<P> >e(p+1);
    FOR(i,1,h){
        string s;cin>>s;
        FOR(j,1,w){
            mp[i][j]=(s[j-1]=='#'?-1:INF);
        }
    }
    struct node{int x,y;};
    queue<node>que;
    FOR(i,1,p){
        int x,y;cin>>x>>y;
        que.push({x,y});
        mp[x][y]=i;
        dis[x][y]=0;
    }
    V<int>fa(p+1);iota(fa.begin(),fa.end(),0);
    auto fin=[&](int x){
        while(x^fa[x]) x=fa[x]=fa[fa[x]];
        return x;
    };
    while(!que.empty()){
        node lls=que.front();que.pop();
        FOR(i,0,3){
            int x=lls.x+xx[i],y=lls.y+yy[i];
            if(x>h||y>w||x<1||y<1)continue;
            if(mp[x][y]==-1)continue;
            if(dis[x][y]==INF){
                dis[x][y]=dis[lls.x][lls.y]+1;
                mp[x][y]=mp[lls.x][lls.y];
                que.push({x,y});
            }else if(mp[x][y]!=mp[lls.x][lls.y]){
                int u=mp[x][y],v=mp[lls.x][lls.y];
                if(u!=v){
                    edge.pb({dis[lls.x][lls.y]+dis[x][y],u,v});
                }
                continue;
            }

        }
    }
    int tot=0;
    sort(edge.begin(),edge.end());
    for(auto i:edge){
        int u=i[1],v=i[2],w=i[0];
        u=fin(u),v=fin(v);
        if(u!=v){
            e[u].pb({v,w});
            e[v].pb({u,w});
            tot++;fa[u]=v;
        }
        if(tot==p-1) break;
    }
    V<int>dep(p+1),siz(p+1),id(p+1),son(p+1),former(p+1),val(p+1),top(p+1),per(p+1);
    int num=0;
    function<void(int,int)>dfs1=[&](int u,int fat){
        per[u]=fat;siz[u]=1;dep[u]=dep[fat]+1;
        for(auto i:e[u]){
            int v=i[0],w=i[1];
            if(v==fat)continue;
            former[v]=w;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(!son[u]||siz[son[u]]<siz[v]) son[u]=v;
        }
    };
    function<void(int,int)>dfs2=[&](int u,int tp){
        top[u]=tp;id[u]=++num;val[num]=former[u];
        if(!son[u]) return;
        dfs2(son[u],tp);
        for(auto i:e[u]){
            int v=i[0];
            if(v!=per[u]&&v!=son[u]) dfs2(v,v);
        }
    };
    FOR(i,1,p){
        if(!id[i]) dfs1(i,0),dfs2(i,i);
    }
    V<V<int> >st(21,V<int>(p+1,0));
    FOR(i,1,p) st[0][i]=val[i];
    for(int i=1;(1<<i)<=p;i++){
        for(int j=1;j+(1<<i)-1<=p;j++){
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
        }
    }
    auto query=[&](int l,int r){
        int k=__lg(r-l+1);
        return max(st[k][l],st[k][r-(1<<k)+1]);
    };
    while(q--){
        int u,v;cin>>u>>v;
        if(fin(u)!=fin(v)) cout<<-1<<"\n";
        else{
            int ans=-INF;
            while(top[u]!=top[v]){
                if(dep[top[u]]<dep[top[v]]) swap(u,v);
                ans=max(ans,query(id[top[u]],id[u]));
                u=per[top[u]];
            }
            if(dep[u]>dep[v]) swap(u,v);
            if(u!=v) ans=max(ans,query(id[u]+1,id[v]));
            cout<<ans<<"\n";
        } 
    }
    return 0;
}