$\texttt{Kruskal}$ 重构树 + 倍增求 $\texttt{LCA}$ 简单题。
题目链接:LibreOJ 2876/JOISC2014 D2T1。
题目
题目描述
原题 pdf
题意翻译
JOI 君所居住的 IOI 市以一年四季都十分炎热著称。
IOI 市被分成 $H$ 行,每行包含 $W$ 块区域。每个区域都是建筑物、原野、墙壁之一。
IOI 市有 $P$ 个区域是建筑物,坐标分别为 $(A _ 1,B _ 1),(A _ 2,B _ 2),\cdots,(A _ P,B _ P)$。
JOI 君只能进入建筑物与原野,而且每次只能走到相邻的区域中,且不能移动到市外。
JOI 君因为各种各样的事情,必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好,但原野上太阳非常毒辣,因此在原野上每走过一个区域都需要 $1$ 升水。此外,原野上没有诸如自动售货机、饮水处之类的东西,因此 IOI 市的市民一般都携带水壶出行。大小为 $x$ 的水壶最多可以装 $x$ 升水,建筑物里有自来水可以将水壶装满。
由于携带大水壶是一件很困难的事情,因此 JOI 君决定携带尽量小的水壶移动。因此,为了随时能在建筑物之间移动,请你帮他写一个程序来计算最少需要多大的水壶。
现在给出 IOI 市的地图和 $Q$ 个询问,第 $i$ 个询问包含两个整数 $S _ i,T _ i$,对于每个询问,请输出:要从建筑物 $S _ i$ 移动到 $T _ i$,至少需要多大的水壶?
数据范围
变量 | 数据范围 |
---|---|
$H,W$ | $1\leq H,W\leq 2000$ |
$P,Q$ | $2\leq P,Q\leq 2\times 10^5$ |
子任务编号 | 分值 | 附加条件 |
$1$ | $10$ | $H,W,P\leq 200$ |
$2$ | $30$ | $P\leq 5000,Q=1$ |
$3$ | $P\leq 5000,Q\leq 10^4$ | |
$4$ | 无 |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
JOISC2014 D2T1 | $5\text{s}$ | $512\text{MiB}$ |
题解
思路
先对整张图进行 $\texttt{BFS}$ 染色,每个点的颜色为到它的最近的建筑编号,权值为最近的距离。

对于两个颜色不同的相邻点 $u,v$,我们不妨记录一条边为 $(\text{color} _ u,\text{color} _ v,\text{dis} _ u+\text{dis} _ v)$。
那么我们显然可以发现,城市 $i$ 到 $j$ 的最小水壶就是对应颜色点之间的最短路径。
我们用 $\texttt{Kruskal}$ 重构树维护即可。
注意事项:原图不一定联通,形成的是 $\texttt{Kruskal}$ 重构森林,不要只从一个点开始搜索。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; const int MAXH=2000+5; const int MAXW=2000+5; const int MAXP=200000+5; const int MAXQ=200000+5; int H,W,p,q; char M[MAXH][MAXW]; int a[MAXP],b[MAXP]; struct Node{ int x,y,d,id; inline Node(reg int x=0,reg int y=0,reg int d=0,reg int id=0):x(x),y(y),d(d),id(id){ return; } }; queue<Node> Q; inline bool check(reg int x,reg int y){ return 1<=x&&x<=H&&1<=y&&y<=W&&M[x][y]=='.'; } bool vis[MAXH][MAXW]; int dis[MAXH][MAXW]; int color[MAXH][MAXW]; inline void BFS(void){ for(reg int i=1;i<=p;++i){ vis[a[i]][b[i]]=true; dis[a[i]][b[i]]=0; color[a[i]][b[i]]=i; Q.push(Node(a[i],b[i],0,i)); } while(!Q.empty()){ static Node t; t=Q.front(); Q.pop(); reg int x=t.x,y=t.y,d=t.d,id=t.id; const int dx[]={-1,0,0,1},dy[]={0,-1,1,0}; for(reg int i=0;i<4;++i){ reg int fx=x+dx[i],fy=y+dy[i]; if(check(fx,fy)) if(!vis[fx][fy]){ vis[fx][fy]=true; dis[fx][fy]=d+1; color[fx][fy]=id; Q.push(Node(fx,fy,d+1,id)); } } } return; } struct Edge{ int from,to,len; inline Edge(reg int from=0,reg int to=0,reg int len=0):from(from),to(to),len(len){ return; } inline bool operator<(const Edge& a)const{ return len<a.len; } }; namespace UnionFind{ int fa[MAXP*2]; inline void Init(reg int size){ for(reg int i=1;i<=size;++i) fa[i]=i; return; } inline int find(reg int x){ if(x==fa[x]) return x; else return fa[x]=find(fa[x]); } inline void merge(reg int a,reg int b){ reg int ra=find(a),rb=find(b); if(ra!=rb) fa[rb]=ra; return; } inline bool search(reg int a,reg int b){ return find(a)==find(b); } } int tot; const int MAXSIZE=MAXH*MAXW; Edge E[MAXSIZE]; namespace Tree{ const int MAXV=MAXP*2; int root; int cnt,head[MAXV],to[MAXV],Next[MAXV]; int v[MAXV],inDeg[MAXV]; inline void Add_Edge(reg int u,reg int v){ Next[++cnt]=head[u]; to[cnt]=v; head[u]=cnt; return; } const int MAXLOG2V=19+1; int fa[MAXV][MAXLOG2V],dep[MAXV]; inline void DFS(reg int ID,reg int father){ fa[ID][0]=father; dep[ID]=dep[father]+1; for(reg int i=1;i<MAXLOG2V;++i) fa[ID][i]=fa[fa[ID][i-1]][i-1]; for(reg int i=head[ID];i;i=Next[i]) DFS(to[i],ID); return; } inline int LCA(int x,int y){ if(dep[x]>dep[y]) swap(x,y); for(reg int i=MAXLOG2V-1;i>=0;--i) if(dep[fa[y][i]]>=dep[x]) y=fa[y][i]; if(x==y) return x; for(reg int i=MAXLOG2V-1;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } } inline void Build(void){ for(reg int i=1;i<=H;++i) for(reg int j=1;j<=W;++j) if(M[i][j]!='#'){ const int dx[]={0,1},dy[]={1,0}; for(reg int k=0;k<2;++k){ reg int fx=i+dx[k],fy=j+dy[k]; if(check(fx,fy)&&color[i][j]!=color[fx][fy]) E[++tot]=Edge(color[i][j],color[fx][fy],dis[i][j]+dis[fx][fy]); } } sort(E+1,E+tot+1); using namespace UnionFind; Init(2*p); reg int pcnt=p; for(reg int i=1;i<=tot;++i) if(!search(E[i].from,E[i].to)){ reg int k=++pcnt; reg int a=find(E[i].from),b=find(E[i].to); Tree::Add_Edge(k,a); Tree::Add_Edge(k,b); ++Tree::inDeg[a]; ++Tree::inDeg[b]; Tree::v[k]=E[i].len; merge(k,a),merge(k,b); } for(reg int i=1;i<=pcnt;++i) if(!Tree::inDeg[i]) Tree::DFS(i,0); return; } int main(void){ scanf("%d%d%d%d",&H,&W,&p,&q); for(reg int i=1;i<=H;++i) scanf("%s",M[i]+1); for(reg int i=1;i<=p;++i) scanf("%d%d",&a[i],&b[i]); BFS(); Build(); while(q--){ static int s,t; scanf("%d%d",&s,&t); reg int lca=Tree::LCA(s,t); if(lca==0) puts("-1"); else{ reg int ans=Tree::v[lca]; printf("%d\n",ans); } } return 0; }
近期评论