poj2236Wireless Network
Description
In the process of repairing the network, workers can take two kinds of operations at every moment, repairing a computer, or testing if two computers can communicate. Your job is to answer all the testing operations.
Input
1. "O p" (1 <= p <= N), which means repairing computer p.
2. "S p q" (1 <= p, q <= N), which means testing whether computer p and q can communicate.
The input will not exceed 300000 lines.
Output
Sample Input
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
Sample Output
FAIL
SUCCESS 这道题可以说是最简单的并查集,直接套模板其实就OK了
现附上AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
struct node{
int a,plug;int x,y;
}com[1010]; //结构体变量存储a:并查集的标准量等于自身;plug:标志量,若为1则电脑修好,为0未修好;(x,y):存储电脑的坐标
int N,d;
int find(int x); //找到祖先
void unite(int i,int p); //合并并查集
int main(){
cin>>N>>d;
char w; //这个变量最扯了,刚开始没有用到这个变量,用的是:fflush(stdin),结果wrong answer,改为%c,&w,吃掉空格换行符就可以,郁闷了。
for(int i=1;i<=N;i++)
scanf("%d%c%d%c",&com[i].x,&w,&com[i].y,&w),com[i].a=i,com[i].plug=0;//电脑坐标,以及初始化
char c;
int p,x,y;
//fflush(stdin);
while(~scanf("%c%c",&c,&w)){
if(c=='O') {
scanf("%d%c",&p,&w);
for(int i=1;i<=N;i++)
if(com[i].plug&&(com[i].x-com[p].x)*(com[i].x-com[p].x)+(com[i].y-com[p].y)*(com[i].y-com[p].y)<=d*d) unite(i,p); //满足条件就合并
com[p].plug=1;
}
else {
scanf("%d%c%d%c",&x,&w,&y,&w);
if(find(x)==find(y)) printf("SUCCESS\n"); //查询是否可以相连
else printf("FAIL\n");
}
//fflush(stdin);
}
return 0;
}
int find(int x){
if(com[x].a==x) return x;
else return com[x].a=find(com[x].a);
}
void unite(int i,int p){
i=find(i),p=find(p);
com[i].a=p;
}
最新文章
- list<;T>; 的使用方法。
- thinkphp自定义标签库
- iOS - OC 异常处理
- css中常用的hack
- jq鼠标点击滚动锚点
- httpsClient实例
- 【和我一起学python吧】初学Python,版本如何选择?
- Redis Sentinel实现Failover
- 在JavaScript的数组中进行数组元素查找和替换(JS的indexOf等)
- bzoj 4244 括号序列dp
- Mybatis的JDBC提交设置/关闭mysql自动提交------关于mysql自动提交引发的惨剧
- 【转】SEGGER Embedded Studio 新建stm32f103工程
- keepalived 高可用配置
- python3 练习题(购物车)
- C#创建自己的扩展方法
- bootstrap增删改查
- centos6.5 redis应用环境搭建
- sql service ---- update和delete 误操作数据 ---- 恢复数据
- Eclipse编译快捷键
- python 函数定义顺序