专栏文章

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

lliangjiande
P14422题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3t3fb
此快照首次捕获于
2025/12/01 20:06
3 个月前
此快照最后确认于
2025/12/01 20:06
3 个月前
查看原文

闲话

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

正文

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

形式化题意

在 H×WH\times W 的二维平面上，存在障碍和 PP 个点。
定义边权：两点之间的最短路径大小。
一共有 QQ 次查询，每次给出两个点，问你两点是否可达。如果可达，请输出两点所经过路径的最大边权的最小值（路径可以是直接的，也可以是经过其他点“绕路”过来的）；否则输出 -1。

暴力

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

正解

发现这个题本质是让我们求图上最小瓶颈路。（不会的看这里）。
你可以这么想：
查询结果是最大边权最小值，那我们要是让边权最小，我们就考虑每次找最小的边，如果这条边可以被替换，就没必要选，否则就选上，直到查询的两点联通（不联通输出 -1）。
然后你做完了这些，你就发现自己“发明”了克鲁斯卡尔，那我们为什么不直接上最小生成树，然后去跑最小瓶颈路呢？
好了，思路上的问题解决了，但是我怎么得到一个图呢？我总不能每个点跑一遍广搜吧？
的确，所以我们考虑只跑一遍广搜，只要加一点点优化。我们在把所有起点塞进队列里，然后染色扩展，当我们发现有一个点的颜色不是空白也不是自己的颜色，说明有起点已经到过了这里，那我们把两个起点之间建一条边，边权为距离减一（题目要求），之后不在这个点扩展。
这样可以保证图上每个点只会被染色一次，遍历不超过两次，而且建出的边只会是两点之间的最短路径长度，数量一定不会很多，就算你悲观估计，边数也不会超过 Θ(H×W)\Theta(H\times W) 的量级。
跑出图后就是最小瓶颈路板子了，我这里用了树链剖分，时间是 Θ(H×W+H×W×log⁡2(H×W)+Q×log⁡2P)\Theta(H\times W+H\times W\times \log _2(H\times W)+Q \times \log _2P)，分别是多源广搜，克鲁斯卡尔和树剖查询的时间。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...