当前位置: 代码迷 >> 综合 >> jzoj1522 无线网络
  详细解决方案

jzoj1522 无线网络

热度:28   发布时间:2023-10-09 10:12:33.0

Description

有一个由n台计算机组成的无线网络。(n <= 1001),正常情况下,每台计算机都能跟与它距离不超过d的任何计算机通讯(d <= 20000)。地震发生了。所有的计算机都陷入瘫痪。专家们试着一台一台地修复计算机,以恢复整个无线网络。有时在修复的过程中,他们需要测试一下某两台计算机能否通讯(如果他们能通过别的正常的计算机进行通讯,也算他们之间可以通讯,即“能否通讯”可以是间接的)。
你的任务,就是模拟修复网络的过程,并回答“能否通讯”的询问。

Input

第一行两个整数,N和d,N表示计算机的数目,d表示两台计算机直接可直接通讯的最大距离。接下来的N行,每行两个整数Xi,Yi,表示每台计算机的坐标。接下来有许多行,每行都是一个操作(或者是修复操作,或者是询问操作)。
操作的格式如下:
O p (1 <= p <= N) 修复操作,表示修复编号为p的电脑;
S p q (1 <= p, q <= N) 询问操作,询问编号为p和编号为q的电脑能否通讯。
如果一台电脑尚未被修复,则它不能和任何电脑通讯。

Output

对于每个询问操作:如果能够通讯,输出一行SUCCESS;如果无法通讯,输出一行FAIL

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

Hint

【限制】
对于50%的数据,N <= 300, 操作次数 <= 10000;
对于100%的数据,N <= 1001, 操作次数 <= 300000。

算法讨论

每修复一台电脑,把与它距离在d内且已修复的电脑放入同一个集合,询问时查询是否同一集合即可。
varf:array[0..1100] of boolean;x,y,t:array[0..1100] of longint;i,l,n,d,k:longint;c:char;
function find(z:longint):longint;
beginif t[z]=z thenexit(z);t[z]:=find(t[z]);exit(t[z]);
end;
procedure lian(v,z:longint);
varvv,zz:longint;
beginvv:=find(v);zz:=find(z);if vv<>zz then t[vv]:=zz;
end;
beginreadln(n,d);for i:=1 to n dobeginreadln(x[i],y[i]);t[i]:=i;end;while not eoln dobeginread(c);if c='O' thenbeginreadln(k);f[k]:=true;for i:=1 to n doif (f[i])and(sqrt(sqr(x[i]-x[k])+sqr(y[i]-y[k]))<=d) thenlian(i,k);endelsebeginreadln(k,l);if (f[k])and(f[l])and(find(k)=find(l)) thenwriteln('SUCCESS')else writeln('FAIL');end;end;
end.