题解：P11829 [TOIP2024] 栖息地分配

_sin_ · 2025-03-31 16:09:45 · 题解

提供一个神秘做法。

先考虑求最小生成树的步骤，如果这条边连接两个不同的连通块，两端颜色可以不同；如果这条边连接在同一个连通块内，两端颜色必须相同。这可以用两个并查集维护。

这个做法看上去很对，但是交上去会 Wa 几个点。我们充分发扬人类智慧，将一条边 (x,y) 当 x>y 时候交换 x,y。最后以 x 为第一关键字，y 为第二关键字从小到大排序。将所有的边这样处理后再进行上述操作即可通过本题。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}

const int N = 1e6+5;
int T,n,m,col[N],cnt=0,st;vector<int>ans[5];
struct EDGE{int x,y;}edges[N];
struct UnionSet{
    int fa[N],n;
    void init(int _n){n=_n;for(int i=1;i<=n;i++)fa[i]=i;}
    int find(int x){return fa[x]=(fa[x]==x?x:find(fa[x]));}
    void merge(int x,int y){fa[find(x)]=find(y);}
}s1,s2;

bool cmp(EDGE a,EDGE b){return a.x==b.x?a.y<b.y:a.x<b.x;}

void solve(){n=read(),m=read();s1.init(n),s2.init(n);for(int i=1;i<=m;i++){
        edges[i].x=read(),edges[i].y=read();if(edges[i].x>edges[i].y)swap(edges[i].x,edges[i].y);
    }sort(edges+1,edges+1+m,cmp);for(int i=1;i<=m;i++)
    if(s1.find(edges[i].x)!=s1.find(edges[i].y))s1.merge(edges[i].x,edges[i].y);
    else s2.merge(edges[i].x,edges[i].y);for(int i=1;i<=n;i++)s2.fa[i]=s2.find(i),col[i]=-1;
    ans[0].clear(),ans[1].clear(),ans[2].clear();for(int i=1;i<=n;i++){
        if(col[s2.fa[i]]==-1)col[s2.fa[i]]=(cnt++)%3;ans[col[s2.fa[i]]].emplace_back(i);
    }for(int id=0;id<3;id++){printf("%ld ",ans[id].size());for(int x:ans[id])printf("%d ",x);puts("");}
}

int main(){
    T=read();while(T--)solve();
    return 0;
}