学步园

题目意思很简单

就是给你n个节点的坐标

有两种操作：

1.修复这个节点

2.询问两个节点是否连通，如果连通，前提是这两个节点都是好的，而且距离要小于等于给出的距离

这个题是一个最简单的并查集模型

#include <stdio.h><br /> #include <string.h><br /> #include <math.h><br /> #define N 1005<br /> int father[N],flag[N];<br /> double map[N][2],dis[N][N];<br /> void make_set(int n)<br /> {<br /> int i;<br /> for(i=0;i<=n;i++)<br /> {<br /> father[i]=i;<br /> }<br /> }<br /> int find_set(int x)<br /> {<br /> if(x!=father[x])<br /> father[x]=find_set(father[x]);<br /> return father[x];<br /> }<br /> void Union(int x,int y)<br /> {<br /> x=find_set(x),y=find_set(y);<br /> father[y]=x;<br /> }<br /> double length(double x1,double y1,double x2,double y2)<br /> {<br /> return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));<br /> }<br /> int main()<br /> {<br /> int n;<br /> double d;<br /> while(scanf("%d%lf",&n,&d)==2)<br /> {<br /> int i,j;<br /> memset(flag,0,sizeof(flag));<br /> make_set(n);<br /> for(i=1;i<=n;i++)<br /> scanf("%lf%lf",&map[i][0],&map[i][1]);<br /> for(i=1;i<=n;i++)<br /> for(j=1;j<=n;j++)<br /> dis[i][j]=length(map[i][0],map[i][1],map[j][0],map[j][1]);<br /> char s[2];<br /> int x,y;<br /> while(scanf("%s",s)!=EOF)<br /> {<br /> if(s[0]=='O')<br /> {<br /> scanf("%d",&x);<br /> flag[x]=1; //表示该节点已经修复<br /> for(i=1;i<=n;i++)<br /> if(flag[i]&&dis[x][i]<=d)//如果距离小于d那么就加入集合<br /> Union(x,i);<br /> }<br /> else<br /> {<br /> scanf("%d%d",&x,&y);<br /> if(find_set(x)==find_set(y))<br /> puts("SUCCESS");<br /> else<br /> puts("FAIL");<br /> }<br /> }<br /> }<br /> return 0;<br /> }