poj2236 Wireless Network(并查集直接套模板
2024-09-07 01:39:13
题目地址:http://poj.org/problem?id=2236
题目大意:n台电脑都坏了,只有距离小于d且被修好的电脑才可以互相联系,联系可传递。输入n和d,n个点的坐标x y。两个操作:O x表示把电脑x修好了,S x y表示询问x和y能否联系。
思路:并查集把能互相联系的电脑都放到同一个集合里(联系可以互相传递),查询的时候只要看x和y是否在一个集合就行了。
另设置两个数组visit[x]表示x是否被修好,dis[x][y]表示x和y之间的距离是否符合要求【先预处理任意两个点之间的距离<=d的标记为1】。
每修好一台电脑记得改变visit标记且把所有和他能联系的电脑合并(距离合适且修好了)。
#include <cstdio> using namespace std; const int maxn = ;
int fa[maxn], visit[maxn], dis[maxn][maxn]; struct node
{
int x, y;
}node[maxn]; //先预处理所有点间的距离
void pre(int n, int d)
{
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
{
int dx = node[i].x - node[j].x;
int dy = node[i].y - node[j].y;
if(dx*dx + dy*dy <= d*d)
dis[i][j] = ;
else
dis[i][j] = ;
}
} void init(int n)
{
for(int i = ; i <= n; i++)
{
fa[i] = i;
visit[i] = ;
}
} int found(int x)
{
if(fa[x] == x)
return x;
return fa[x] = found(fa[x]);
} void unite(int x, int y)
{
int px = found(x);
int py = found(y);
if(px == py)
return;
else
fa[px] = py;
} int main()
{
int n, d, x, y;
char opr;
scanf("%d%d", &n, &d);
init(n);
for(int i = ; i <= n; i++)
scanf("%d%d", &node[i].x, &node[i].y);
pre(n, d);//pre要写在输入坐标之后!!!!不然dis就全是1!!!
getchar();
while(scanf("%c", &opr) == )
{
if(opr == 'O')
{
scanf("%d", &x);
visit[x] = ;
for(int i = ; i <= n; i++)
if(visit[i] && dis[x][i])//距离合适且修好了的就可以互相联络
unite(x, i);//能互相联络的都放一个集合里
}
else
{
scanf("%d%d", &x, &y);
if(found(x) == found(y))
printf("SUCCESS\n");
else
printf("FAIL\n");
}
getchar();
}
return ;
}
【pre(n, d)要放到输入坐标之后!!!!!!因为要用到坐标!!!!!!!!不然dis全是1!!!!!!!!!!!!!!!!!!!!!!!】
最新文章
- redmine问题集锦
- 理清C++常量指针和指针常量这团乱麻
- oracle中TO_CHAR与TO_DATE
- discuz怎么根据连接知道调用的是什么模板页面
- [转]深入理解Flash Player重绘
- 【32】确定你的public继承塑模出Is-A关系
- Linux下OpenSSL 安装图文详解
- C语言之进制
- 【转】Java 内部类种类及使用解析
- 解决thymeleaf layout布局不生效
- Web API <;五>; 序列化
- javascript模块化编程库require.js的用法
- linear-gradient 纯CSS3项目价格表切换代码
- [转帖] bat方式遍历目录内的文件
- poj2054 Color a Tree
- How to set up github to work with Visual Studio 2013
- alias 设置别名
- jQuery UI的datepicker()与变更格式
- Js_图片轮换
- 浏览器中回车(Enter)和刷新的区别是什么?[转载]