P1196 [NOI2002]银河英雄传说 【带权并查集】
2024-09-06 19:47:24
思路
用sum记录每个舰队的战舰数量, tohead 记录当前舰离舰首的距离,那么求任意两舰之间有多少舰显然就是 abs( tohead[i] - tohead[j] ) - 1;
CODE
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0) using namespace std;
typedef long long LL; template<class T>inline void read(T &res)
{
char c;T flag=;
while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';
while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;
} namespace _buff {
const size_t BUFF = << ;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
if (ib == ie) {
ib = ibuf;
ie = ibuf + fread(ibuf, , BUFF, stdin);
}
return ib == ie ? - : *ib++;
}
} int qread() {
using namespace _buff;
int ret = ;
bool pos = true;
char c = getc();
for (; (c < '' || c > '') && c != '-'; c = getc()) {
assert(~c);
}
if (c == '-') {
pos = false;
c = getc();
}
for (; c >= '' && c <= ''; c = getc()) {
ret = (ret << ) + (ret << ) + (c ^ );
}
return pos ? ret : -ret;
} const int maxn = 5e4 + ; int fa[maxn];
int tohead[maxn], sum[maxn];
int t; int fid(int x) {
if(fa[x] == x) {
return x;
}
int r1 = fa[x], r2 = fid(fa[x]);
fa[x] = r2;
tohead[x] += tohead[r1];
return r2;
} void join(int x, int y) {
int fx = fid(x), fy = fid(y);
fa[fy] = fx;
tohead[fy] = sum[fx];
sum[fx] += sum[fy];
sum[fy] = ;
} int main()
{
scanf("%d",&t);
for ( int i = ; i <= ; ++i ) {
fa[i] = i;
sum[i] = ;
}
while(t--) {
char s[];
int x, y;
cin >> s;
scanf("%d %d",&x, &y);
if(s[] == 'M') {
join(x, y);
}
else {
if(fid(x) != fid(y)) {
printf("-1\n");
continue;
}
else {
printf("%d\n",abs(tohead[x] - tohead[y]) - );
}
}
}
return ;
}
最新文章
- Reactive Extensions介绍
- [转]Python 中的 lambda,filter,map,reduce,apply
- valuestack,stackContext,ActionContext.之间的关系以及如何存取数值的
- SlimDX.dll安装之后所在位置
- 关于Json处理的两个实例
- 【转】 Android 开发 之 JNI入门 - NDK从入门到精通
- 给分类(Category)添加属性
- SQL Server 2012数据库还原所遇到的问题
- Spring MVC中各个filter的用法
- add jars和add external jars有什么区别
- python 面向对象编程(一)
- 第2章 rsync算法原理和工作流程分析
- C#图像显示实现拖拽、锚点缩放功能【转】
- js截取url参数
- asp.net mvc6+ef框架做的书籍管理项目
- Laravel 返回数据库中的随机一行数据
- Tensorflow数据读取的方式
- 精巧好用的DelayQueue
- 应用程序-特定 权限设置并未向在应用程序容器 不可用 SID (不可用)中运行的地址 LocalHost (使用 LRPC) 中的用户
- 基于jQuery点击圆形边框弹出图片信息