电影站的seo,购物网站怎么做代码,网站计费系统怎么做,猪八戒兼职网问题#xff1a;
地震发生在东南亚。 ACM#xff08;亚洲合作医疗团队#xff09;已经与膝上电脑建立了无线网络#xff0c;但是一次意外的余震袭击#xff0c;网络中的所有计算机都被打破了。计算机一个接一个地修复#xff0c;网络逐渐开始工作。由于硬件限制#xf…问题
地震发生在东南亚。 ACM亚洲合作医疗团队已经与膝上电脑建立了无线网络但是一次意外的余震袭击网络中的所有计算机都被打破了。计算机一个接一个地修复网络逐渐开始工作。由于硬件限制每台计算机只能直接与距离它不远的计算机进行通信。但是每台计算机都可以被视为两台计算机之间通信的中介也就是说如果计算机A和计算机B可以直接通信或者计算机C可以与A和b进行通信则计算机A和计算机B可以进行通信。
在修复网络的过程中工作人员可以随时进行两种操作修复计算机或测试两台计算机是否可以通信。你的工作是回答所有的测试操作。 输入 第一行包含两个整数N和d1 N 1001,0 d 20000。这里N是计算机的数量编号从1到ND是两台计算机可以直接通信的最大距离。在接下来的N行中每行包含两个整数xiyi0 xiyi 10000这是N台计算机的坐标。从第N 1行到输入结束有一些操作这些操作是一个接一个地执行的。每行包含以下两种格式之一的操作 1.“O p”1 p N表示修复计算机p。 2.“S p q”1 pq N这意味着测试计算机p和q是否可以通信。
输入不会超过300000行。 产量 对于每个测试操作如果两台计算机可以通信则打印“SUCCESS”否则打印“FAIL”。 Sample Input 注意0和o啊。。
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
分析与解答
我一开始没读懂提1和2和4修好了那2可以与3连4可以与3连为啥1和四不能连后来我明白了修好的电脑能连与他距离小于等于d的修好的电脑。而不是说小于d的电脑都能与之连。就是说可以通信的计算机一定都是已经修好的计算机而且两台修好的计算机的距离还必须小于等于给定的那个距离。
编号从1-n只不过这里的电脑多了个坐标多了个距离的判断。 并查集里放的是相连的电脑编号最后找也是找电脑编号的根
代码参考https://blog.csdn.net/superxtong/article/details/51875835
#includecstdio
#includecstring
int pre[10100 ];
int find(int x) //查找根节点
{ int rx;while ( pre[r] ! r ) //返回根节点 rrpre[r];int ix , j ;while( i ! r ) //路径压缩{j pre[ i ]; //j是i的原来的父结点 pre[ i ] r ; //现在把i的父结点改成根节点 ij; //再把j的父节点改成根节点 }return r ;
}
void join(int x,int y) //判断x y是否连通//如果已经连通就不用管了 如果不连通就把它们所在的连通分支合并起,
{int fxfind(x),fyfind(y);if(fx!fy)pre[fx ]fy;
}
struct xyz{int x;int y;
};
xyz a[10086];
int flag[10086];
int main(){memset(flag,0,sizeof(flag));int n,d;scanf(%d%d,n,d);for(int i1;in;i){pre[i]i;scanf(%d%d,a[i].x,a[i].y);}char ch;while(scanf( %c,ch)!EOF){if(chO){int k;scanf(%d,k);flag[k]1;for(int i1;in;i){if(flag[i]i!k){if((a[i].x-a[k].x)*(a[i].x-a[k].x)(a[i].y-a[k].y)*(a[i].y-a[k].y)d*d)join(i,k);}}}if(chS){int x1,y1;scanf(%d%d,x1,y1);if(find(x1)find(y1))printf(SUCCESS\n);elseprintf(FAIL\n);}}
}
