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

· · 题解

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

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

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

那么边权呢？

我们分类讨论一下，设当前点为 (x_a,y_a)，找到的点为 (x_b,y_b)，找到的点纵坐标更大。画图发现，对于左右两列的点，只要过了 (x_b - x_a) 天，它们就联通，对于同一列的点，过了 (x_b - x_a -1) 天，它们就联通。

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

代码

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