【BZOJ 3376】[Usaco2004 Open]Cube Stacking 方块游戏 带权并查集
2024-08-29 10:29:06
这道题一开始以为是平衡树结果发现复杂度过不去,然后发现我们一直合并而且只是记录到最低的距离,那么就是带权并查集了,带权并查集的权一般是到根的距离,因为不算根要好打,不过还有一些其他的,具体的具体打。
#include <cstdio>
#include <cstring>
const int N=;
int h[N],f[N],size[N];
char s[];
inline int find(int x){
if(f[x]==x)return x;
int temp=f[x];f[x]=find(f[x]);
if(temp!=f[x])h[x]+=h[temp];
return f[x];
}
inline void Unit(int x,int y){
h[find(x)]=size[find(y)];
size[find(y)]+=size[find(x)];
f[find(x)]=find(y);
}
int main(){
int T,x,y;scanf("%d",&T);
for(int i=;i<N;i++)f[i]=i,size[i]=,h[i]=;
while(T--){
scanf("%s",s);
if(s[]=='M')scanf("%d%d",&x,&y),Unit(x,y);
else scanf("%d",&x),find(x),printf("%d\n",h[x]);
}
}
最新文章
- 如何发布一个Mac应用并使其成为全球付费榜第一
- tweenmax.js 文档
- Bootstrap 3 简介
- 【系统移植】Android系统移植
- [杂]SQL Server 之 Understanding Connection Pooling and Transactions
- getattr的作用是什么呢
- layer
- LINQ标准查询操作符(二)——Join、GroupJoin、GroupBy、Concat、
- strcpy函数导致release版程序崩溃
- Android 编程下的计时器
- 安装linux工作环境
- SpringMVC-HelloWorld (XML)
- linux发行版和内核的关系
- TensorFlow-相关 API(学习笔记 )
- Python中byte与str
- bash shell while语法
- Oracle 连接查询
- 用一句sql语句更新两个表并可更新对应的字段的值
- WEB学习笔记12-高可读性的HTML之如何正确设计表单
- SQL Server 异常解决:语句被终止。完成执行语句前已用完最大递归 100。