hdu 2860 Regroup（并查集）
2024-08-27 05:53:13
题意：
AP x y
A recruit with ability rate x were asked to join company y. (0<=x<2^31, 0<=y<n)
MG x y
Company x and company y is merged. The new company is numbered as x. (0<=x, y<n)
GT x
Report the fighting capacity of company x. (0<=x<n)
思路：
并查集，判断好各种可能的情况。
代码：
int n,k,m;
int fa[100005], ability[100005]; int findFa(int x){
if(fa[x]==x)
return fa[x];
int t=fa[x];
fa[x]=findFa(fa[x]);
ability[x] = min( ability[x],ability[t] );
return fa[x];
} int main(){ while(scanf("%d%d%d",&n,&k,&m)!=EOF){
rep(i,0,n-1){
fa[i]=i;
ability[i]=inf;
} rep(i,1,k){
int rate,belongTo;
scanf("%d%d",&rate,&belongTo);
ability[belongTo]=min( ability[belongTo],rate );
}
while(m--){
char ope[5];
scanf("%s",ope);
if(ope[0]=='A'){
int x,y;
scanf("%d%d",&x,&y);
int faTemp=findFa(y);
if(y!=faTemp){
puts("Reject");
}else{
ability[faTemp]=min( ability[faTemp],x );
puts("Accept");
}
}
else if(ope[0]=='M'){
int x,y;
scanf("%d%d",&x,&y);
int fx=findFa(x);
int fy=findFa(y);
if(fx!=x || fy!=y || fx==fy){
puts("Reject");
}else{
ability[fx]=min( ability[fx],ability[fy] );
fa[fy]=fx;
puts("Accept");
}
}
else{
int x;
scanf("%d",&x);
int fx=findFa(x);
if(x!=fx){
printf("Company %d is a part of company %d.\n",x,fx);
}
else{
if(ability[x]==inf){
printf("Company %d is empty.\n",x);
}else{
printf("Lowest rate: %d.\n",ability[x]);
}
}
}
}
puts(""); } return 0;
}
最新文章
- JAVA的模式对话框和非模式对话框
- android应用安全——（数据抓包）跟踪监控android数据包
- Neutron 理解 (1): Neutron 所实现的虚拟化网络 [How Netruon Virtualizes Network]
- 洛谷P3390 【模板】矩阵快速幂
- bnuoj 24251 Counting Pair
- 黑马程序员：Java编程_String
- 蓝牙（Profile）构成
- Java中的栈：java.util.Stack类
- js实现楼层效果
- memcpy源代码
- reincarnation server
- java正则表达式获取指定HTML标签的指定属性值
- seq语句随笔
- LeetCode之“链表”：Linked List Cycle && Linked List Cycle II
- [物理学与PDEs]第1章第2节 预备知识 2.2 Ampere-Biot-Savart 定律, 静磁场的散度与旋度
- K-means算法的matlab程序（初步）
- 计算机基础+python安装注意问题+python变量介绍
- mysql 在update中实现子查询的方式
- webapi中使用swagger
- 洛谷 P2431 正妹吃月饼 解题报告