题解：P14501 [NCPC 2025] Gotta Trade Some of 'Em

· · 题解

题号：P14501

题目链接：P14501 [NCPC 2025] Gotta Trade Some of 'Em

题目简述：

题目给我们 n 个小孩，m 个关系，并且有 k 个 Pokémon 版本。要我们通过分配 Pokémon 版本使每个小孩都有方式获得可能其他 Pokémon 版本中独有的 Pokémon。

思路：

这道题很显然，是一道并查集的板子题。
为什么呢？因为我们想一下：

如果孩子 1 认识孩子 2，孩子 2 认识孩子 3。
那么孩子 1 就可以利用孩子 2 间接与孩子 3 交易。

也就是说可以将孩子 1，孩子 2 和孩子 3 连在一起。表示这三人可以通过直接或间接方式互相交易。
那么我们就要用到 并查集 了。

并查集

这是 oiwiki 里并查集的定义：
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

其实就是给数分了个组。用一个数组来存储这个点所属的集的编号。

并查集可以实现两种操作：

1.查

假如有一个数组，我们我们定义 f_i 为第 i 个数所属的集合编号。
并查集是需要初始化的，就把数组中的每一个数的集合编号都赋值为下表就可以了。
我们会在下面涉及到并的操作，使某些数的集合编号改变。所以我们用以下函数实现查的操作：

inline int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}

这是什么意思呢？
意思是如果 x=f_x 的话说明这个数的集合编号为它自己的下标，直接返回 x 即可。
可如果不一样，说明它现在的集合编号所在的集合改变了，需要再次查找 f_x 所在的集合，然后递归。

2.并

现在我们想要将第 x 个数与第 y 个数合并。

第一步是先判断一下这两个数是否处于同一集合。如果不是，再进行下一步操作：
将第 f_{find(x)} 改为 find(y) 就好了。意思是将第 find(x) 个数的集合添加到第 find(y) 个数的集合里。其深意可以自己想一想，理解后的记忆更深刻。

构造答案

我们现在处理完 n 个小孩的关系后，该考虑如何分配了。

为了让每一个小孩都可以收集到所有版本中的 Pokémon，我们尽量让每个集合内的小孩拥有的 Pokémon 版本不一致。下面有一个例子可供理解：

假设有 3 个小孩属于同一集合，可是有 4 种 Pokémon 版本，那么最优的分配方式也会使他们可能差一个版本的 Pokémon 收集不到。因为这三个小孩最多有三种 Pokémon，总会有一个 Pokémon 版本的独有的 Pokémon 收集不到。
可如果有 3 种 Pokémon 版本，那他们一人一种版本正好。
这就是判断如果不存在任何分配方式可以使所有孩子填满 Pokédex 的方法：n<k（n 为集合中元素的数量）。我们知道，我们在此题里的每个集合中的任意两个孩子之间都可以通过直接或间接方式进行交易，所以我们只需最大化每个集合中的 Pokémon 版本数量就好了。

如果有解，我们就让集合中前 k 个小孩一人一种不同的版本，然后其他的随便即可。

代码：

#include<bits/stdc++.h>
typedef long long ll;
template<typename T>inline void read(T&x){
    x=0;char c;int sign=1;
    do{c=getchar();if(c=='-') sign=-1;}while(!isdigit(c));
    do{x=x*10+c-'0';c=getchar();}while(isdigit(c));
    x*=sign;
}
int n,m,k;
int x,y;
int f[100005],z[100005],c[100005];
inline int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}//查
int main(){
    read(n),read(m),read(k);
    for(int i=1;i<=n;i++) f[i]=i;
    while(m--){
        read(x),read(y);
        if(find(x)!=find(y)) f[find(x)]=find(y);//并
    }
    for(int i=1;i<=n;i++) z[find(i)]++;//计算集合编号为 find(i) 的集合中的元素数量
    for(int i=1;i<=n;i++){
        if(z[i]&&z[i]<k){//判断是否有解
            printf("impossible");
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(c[f[i]]==k) c[f[i]]=0;//避免版本号越界
        printf("%d ",++c[f[i]]);//输出
    }
    return 0;
}

代码总结：

代码不难，并查集 的题都挺简单的。

题目总结：

这道题涉及 并查集。比较简单，可以用来练练手，刷刷手感。