poj 2236 Wireless Network

发布时间:2016-12-8 10:01:30 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 2236 Wireless Network",主要涉及到poj 2236 Wireless Network方面的内容,对于poj 2236 Wireless Network感兴趣的同学可以参考一下。

  我的方法是暴力加并查集的方法,vis数组记录这个电脑是否已经修好,我用一个map数组记录各个点的之间距离的平方,然后每次输入O字符是,就进行一个暴力,只要距离在d*d范围内的就将其连在一起。如果输入的是S的话,直接就进行查找然后判断其是否在同一个集合中。  注意下,O,S序列是以EOF结束的。   #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N = 1005; int n, d; int fa[N], map[N][N]; bool vis[N]; typedef struct { int x,y; }Node; Node arr[N]; void ini() { for(int i=1; i<=n; ++i) { vis[i] = false; fa[i] = i; } } int fint(int a) { if(fa[a] != a) fa[a] = fint(fa[a]); return fa[a]; } void uni(int a,int b) { a = fint(a); b = fint(b); if(a != b) fa[a] = b; } int main(void) { cin >> n >> d; ini(); d *= d; for(int i=1; i<=n; ++i) scanf("%d %d",&arr[i].x,&arr[i].y); for(int i=1; i<=n; ++i) for(int j=i; j<=n; ++j) { map[i][j] = map[j][i] = (arr[i].x - arr[j].x)*(arr[i].x - arr[j].x) + (arr[i].y - arr[j].y)*(arr[i].y - arr[j].y); } getchar(); char ch; int a,b; while(scanf("%c",&ch)!=EOF) { if(ch=='O') { scanf("%d",&a); vis[a] = true; for(int e=1; e<=n; ++e) if(vis[e]&&e!=a&&map[e][a]<=d) uni(e,a); } else { scanf("%d %d",&a,&b); if(fint(a)==fint(b)) { printf("SUCCESS\n"); } else printf("FAIL\n"); } getchar(); } return 0; }

上一篇:Android中使用代码截图的各种方法总结
下一篇:QT国际化示例, 检测系统语言,设置适合语言,按键切换显示语言

相关文章

相关评论