题目地址: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!!!!!!!!!!!!!!!!!!!!!!!】

最新文章

  1. redmine问题集锦
  2. 理清C++常量指针和指针常量这团乱麻
  3. oracle中TO_CHAR与TO_DATE
  4. discuz怎么根据连接知道调用的是什么模板页面
  5. [转]深入理解Flash Player重绘
  6. 【32】确定你的public继承塑模出Is-A关系
  7. Linux下OpenSSL 安装图文详解
  8. C语言之进制
  9. 【转】Java 内部类种类及使用解析
  10. 解决thymeleaf layout布局不生效
  11. Web API &lt;五&gt; 序列化
  12. javascript模块化编程库require.js的用法
  13. linear-gradient 纯CSS3项目价格表切换代码
  14. [转帖] bat方式遍历目录内的文件
  15. poj2054 Color a Tree
  16. How to set up github to work with Visual Studio 2013
  17. alias 设置别名
  18. jQuery UI的datepicker()与变更格式
  19. Js_图片轮换
  20. 浏览器中回车(Enter)和刷新的区别是什么?[转载]

热门文章

  1. 吴裕雄--天生自然Numpy库学习笔记:NumPy 排序、条件刷选函数
  2. C语言-错误处理
  3. 3、gitlab备份与恢复
  4. js学习:基本数据类型
  5. 第1节 Scala基础语法:13、list集合的定义和操作;16、set集合;17、map集合
  6. Linux命令:ss命令
  7. 《容器化.NET应用架构指南》脑图学习笔记(第一部分)
  8. Eclipse java SE版本解决无法新建web项目问题
  9. Codeforces1301D
  10. luogu P3356 火星探险问题