题解：P13736 [JOIGST 2025] 日本浮现 / Japan Emerges

看到这种带有至少字样的题目，我们的第一反应应该是~~二分答案~~最小生成树！

没错，这题是一道最小生成树的题目，关键在于建边。

不难发现，对于一个点

(x,y)

，它可以联通的点只能是左边一列、当前列、右边一列上的点，这里用二分查找就可以了。为了保证不重复连边，每个点只连向更深的点。

那么边权呢？

我们分类讨论一下，设当前点为

(x_a,y_a)

，找到的点为

(x_b,y_b)

，找到的点纵坐标更大。画图发现，对于左右两列的点，只要过了

(x_b - x_a)

天，它们就联通，对于同一列的点，过了

(x_b - x_a -1)

天，它们就联通。

那么边权就是上面说的三种，套一个克鲁斯卡尔板子就可以过了。

代码

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;
using T=array<int,3>;
using P=array<int,2>;
struct node{int x,y;};
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return x*f;
}
signed main(){
	int h=read(),w=read(),n=read();
	V<V<P> >mp(w+2);
	V<node>a(n+1);
	FOR(i,1,n)a[i].x=read(),a[i].y=read(),mp[a[i].y].pb({a[i].x,i});
	FOR(i,1,w) sort(mp[i].begin(),mp[i].end());
	V<int>fa(n+1);iota(fa.begin(),fa.end(),0);
	auto fin=[&](int x){
		while(x^fa[x]) x=fa[x]=fa[fa[x]];
		return x;
	};
	V<T>e;
	FOR(i,1,n){
		auto it=lower_bound(mp[a[i].y].begin(),mp[a[i].y].end(),P{a[i].x+1,0});
		if(it!=mp[a[i].y].end()){
			auto t1=*it;
			e.pb({t1[0]-a[i].x-1,i,t1[1]});
		}
		if(!mp[a[i].y-1].empty()){
			it=lower_bound(mp[a[i].y-1].begin(),mp[a[i].y-1].end(),P{a[i].x,0});
			if(it!=mp[a[i].y-1].end()){
				auto t1=*it;
				e.pb({t1[0]-a[i].x,i,t1[1]});
			}
		}
		if(!mp[a[i].y+1].empty()){
			it=lower_bound(mp[a[i].y+1].begin(),mp[a[i].y+1].end(),P{a[i].x,0});
			if(it!=mp[a[i].y+1].end()){
				auto t1=*it;
				e.pb({t1[0]-a[i].x,i,t1[1]});
			}
		}
	}
	int tot=0;
	sort(e.begin(),e.end());
	for(auto i:e){
		int u=i[1],v=i[2],w=i[0];
		if(fin(u)!=fin(v)){
			tot++;
			fa[fin(u)]=fin(v);
			if(tot==n-1){
				cout<<w;
				return 0;
			}
		}
	}
	cout<<-1;
	return 0;
}

题解：P13736 [JOIGST 2025] 日本浮现 / Japan Emerges

文章操作

代码

相关推荐

评论

题解：P13736 [JOIGST 2025] 日本浮现 / Japan Emerges