博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ-2236 Wireless Network---并查集
阅读量:6402 次
发布时间:2019-06-23

本文共 1580 字,大约阅读时间需要 5 分钟。

题目链接:

 

题目大意:

给你N台电脑,从1-N。一个数字,表示两台计算机的最大通信距离,超过这个距离就无法进行通信。然后分别告诉这些电脑的坐标,接下来有两种操作,第一种O表示这点电脑修好,第二种S,表示测试这两台电脑能不能进行正常的通信

思路:

首先需要注意,只有某台电脑修好了,这台电脑才可以参加通信。

并查集的简单应用,对每次修好的电脑对其它已经修好的电脑遍历,如果距离小于等于最大通信距离就将他们合并。之后判断2台电脑是不是一个集合中就KO了

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 using namespace std;11 typedef pair
Pair;12 typedef long long ll;13 const int INF = 0x3f3f3f3f;14 int T, n, m, d;15 const int maxn = 1e3 + 10;16 bool vis[maxn];//vis[i] = 1表示第i台电脑已经修好17 int pa[maxn];18 vector
G[maxn];19 struct node20 {21 int x, y;22 }a[maxn];23 int dis(node a, node b)24 {25 return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);26 }27 void init()28 {29 for(int i = 1; i <= n; i++)scanf("%d%d", &a[i].x, &a[i].y);30 for(int i = 1; i <= n; i++)31 {32 for(int j = i + 1; j <= n; j++)33 if(dis(a[i], a[j]) <= d * d)G[i].push_back(j), G[j].push_back(i);34 }35 for(int i = 0; i <= n; i++)pa[i] = i;36 }37 int Find(int x)38 {39 return x == pa[x] ? x : pa[x] = Find(pa[x]);40 }41 int main()42 {43 cin >> n >> d;44 init();45 string s;46 int x, y;47 while(cin >> s)48 {49 if(s[0] == 'O')50 {51 scanf("%d", &x);52 vis[x] = 1;53 for(int i = 0; i < G[x].size(); i++)54 {55 y = G[x][i];56 if(vis[y])57 {58 pa[Find(y)] = Find(x);59 //这里必须是pa[Find(y)] = Find(x)不能是pa[y] = x,因为是并查集根节点的更改60 }61 }62 }63 else if(s[0] == 'S')64 {65 scanf("%d%d", &x, &y);66 //cout<
<<" "<
<

 

转载于:https://www.cnblogs.com/fzl194/p/8819598.html

你可能感兴趣的文章
设计模式java----单例模式
查看>>
西西弗的石头----读《哲学家都干了些什么》有感
查看>>
【OCR技术系列之二】文字定位与切割
查看>>
【300】◀▶ IDL - ENVI API
查看>>
Docker初体验
查看>>
UBUNTU LINUX中连接ANDROID 小米真机调试
查看>>
[转] Zend Framework 中 htaccess 的标准配置
查看>>
linux就是这个范儿之融于心而表于行(1)
查看>>
maven安装配置部署建项运行
查看>>
node爬虫
查看>>
接口测试之JMeter初探
查看>>
Docker背后的内核知识——cgroups资源限制(转)
查看>>
Java技术——Java泛型详解(转)
查看>>
某个第三方支付平台数据库的分析、学习与总结(转)
查看>>
Linux Linux程序练习八
查看>>
读书笔记:《写给大家看的设计书》
查看>>
Predicate与filter
查看>>
UITableViewCell 取消分隔线
查看>>
性能测试工具 nGrinder 项目剖析及二次开发
查看>>
Mybatis集成pagehelper and jsqlparser(分页)
查看>>