题解 P1456 【Monkey King】
cjh20090318
2022-05-10 19:43:34
（上一次更新： 2022-06-02 19:40 ，修改了乱加空格的问题，以及函数 merge 的命名）
大家好，我是 CQ-FZOIer，C2024 级蒟蒻 CJH。[洛谷博客](https://www.luogu.com.cn/blog/Chen-Jinhui/solution-p1456)
最近我们学了堆，接着学了并查集，老师就为我们布置了这一道题目 [Monkey King](https://www.luogu.com.cn/problem/P1456) 了。 ~~我们还没有学左偏树，所以看不懂各位大佬的左偏树题解。~~ 我决定换一种更浅显的方式，也就是……
**堆+并查集**的方法来 AC 此题！！！
下面……
### 开始切入正题，分析题目：
1. 有 $N$ 只猴子，于是我们就要创建 $N$ 个大根堆。
2. 还需要长度为 $N$ 的 father 数组，用来储存猴子的根，$fa_i$ 表示第 $i$ 个猴子的根。
3. 当两只猴子打斗时，可以通过并查集的**找根**（find）来查找猴子的根：
```cpp
int find(int x){//找猴子x的根
//循环查找
/*while(x!=fa[x]){
x=fa[x];
}
return x;*/
//递归查找
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
```
4. 根据题意，如果根相等（也就是互相认识），则输出 $-1$；否则从两只猴子的团队中取出（top&pop）强壮最大值（堆顶），分别除以 $2$ 后再放回堆中（push）。
5. 接着用并查集进行**按秩合并**（merge）：
```cpp
void merge(int x,int y){//合并x,y
int f1=find(x),f2=find(y);//找到两只猴子的根
if(f1==f2)//如果为同一个根
printf("-1\n");
else{
int at=a[f1].top(),bt=a[f2].top();
a[f1].pop();a[f2].pop();
at/=2;bt/=2;//按照题目要求减少一半
a[f1].push(at);a[f2].push(bt);//放回原堆中
if(a[f1].size()<a[f2].size()){//按秩合并，减少循环次数。
//合并
fa[f1]=f2;
//将一对元素全部移至f2
while(!a[f1].empty()){
int tmp=a[f1].top();
a[f1].pop();
a[f2].push(tmp);
}
//输出最大值
printf("%d\n",a[f2].top());
}
else{
//同上
fa[f2]=f1;
while(!a[f2].empty()){
int tmp=a[f2].top();
a[f2].pop();
a[f1].push(tmp);
}
printf("%d\n",a[f1].top());
}
}
}
```
### 注意事项
题目可能有**多组数据**！！！所以我们应该一直读入至**文件结束符 EOF**。
### 具体详见代码（请勿抄袭！！！）：
```cpp
//the code is from chenjh
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[100001];//存储每只猴子的根
priority_queue <int> a[100001];//维护的堆
//函数都在后面！！！
int find(int x);//找根
void merge(int x,int y);//合并
int main(){
while(scanf("%d",&n)!=EOF){//有多组数据，需要一直读入到文件结束符EOF
//需要清空堆！
for(int i=0;i<=100000;i++){
while(!a[i].empty())
a[i].pop();
}
//将根先设为自己
for(int i=1;i<=n;i++) fa[i]=i;
//读入实力值，存储至堆中
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
a[i].push(x);
}
//进行打斗
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
merge(x,y);//合并
}
}
return 0;
}
int find(int x){
//循环找根
/*while(x!=fa[x]){
x=fa[x];
}
return x;*/
//递归找根
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
int f1=find(x),f2=find(y);//找到两只猴子的根
if(f1==f2)//如果为同一个根
printf("-1\n");
else{
int at=a[f1].top(),bt=a[f2].top();
a[f1].pop();a[f2].pop();
at/=2;bt/=2;//按照题目要求减少一半
a[f1].push(at);a[f2].push(bt);//放回原堆中
if(a[f1].size()<a[f2].size()){//按秩合并，减少循环次数。
//合并
fa[f1]=f2;
//将一对元素全部移至f2
while(!a[f1].empty()){
int tmp=a[f1].top();
a[f1].pop();
a[f2].push(tmp);
}
//输出最大值
printf("%d\n",a[f2].top());
}
else{
//同上
fa[f2]=f1;
while(!a[f2].empty()){
int tmp=a[f2].top();
a[f2].pop();
a[f1].push(tmp);
}
printf("%d\n",a[f1].top());
}
}
}
```
如有错误，欢迎*批评指正*，本人将**尽快修改**。
*谢谢查看！*
此题是本人 AC 的**第一道紫题**，更是本人写的**第一篇题解**！