并查集——POJ-2236_weixin_30734435的博客-程序员宅基地

题目含义

给出一堆坏的电脑的坐标和一系列操作

好的电脑如果距离小于等于d可以看做一个集合

然后O是修电脑,S是询问两个电脑在不在一个集合

题目分析

明显的并查集问题,只是要标识好的和坏的电脑,然后只能在好的电脑用并查集

注意:如果让【新修好的电脑】的父亲指向【之前修好的电脑】的话

可能会出错,本该在一个集合的电脑在不同集合了

这样的话,就把【之前修好的电脑】的父亲指向【新修好的电脑】这样就不会出错了

题目代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1007;
int n,d,p,q,repair[maxn],f[maxn];
char s[2];
struct node{
    int x,y,ok;
}com[maxn];
int dis(node a,node b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int get(int x){
    if(f[x]==x)return x;
    else return f[x]=get(f[x]);
}
int main(){
    scanf("%d%d",&n,&d),d=d*d;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&com[i].x,&com[i].y);
        com[i].ok=0;
        f[i]=i;
    }
    int cnt=0;
    while(~scanf("%s%d",&s,&p)){
        if(s[0]=='O'){
            com[p].ok=1;
            repair[cnt++]=p;
            for(int i=0;i<cnt-1;i++){
                int fx=get(repair[i]),fy=get(p);
                if(dis(com[p],com[repair[i]])<=d)
                    f[fx]=fy;
            }
        }
        else if(s[0]=='S'){
            scanf("%d",&q);
            int fx=get(p),fy=get(q);
            if(fx==fy&&com[p].ok&&com[q].ok)printf("SUCCESS\n");
            else printf("FAIL\n");
        }
    }
    return 0;
}

 

转载于:https://www.cnblogs.com/helman/p/11234278.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30734435/article/details/97240709

智能推荐

乘法命令linux,如何在Linux命令行中做基础数学计算/数值运算_Juice-emi的博客-程序员宅基地

Linux bash或命令行可让您执行基本和复杂的算术和布尔运算。诸如expr,jot,bc和factor等命令可帮助您找到复杂问题的最佳数学解决方案。在本文中,我们将描述这些命令并提供示例,这些示例将成为您转向更有用的数学解决方案的基础。这里以Ubuntu为例,我们已经在Ubuntu 18.04 LTS系统上运行了本文中提到的命令和过程。其他基于LINUX系统终端也一样可以用这里的命令!我们使用...

小米手机拦截返回音设置不了_烦人的骚扰电话该怎么有效拦截?其实很简单,以小米手机为例..._weixin_39713686的博客-程序员宅基地

相信很多人都在日常生活中受到骚扰电话的困扰,从周一到周日,这些骚扰电话从未停止。周一刚上班,正在开会,来了一个,还么开完,又来了一个。周末,你还在睡觉,被骚扰电话吵醒。有一天,你有时间了,想接一个聊聊,结果发现是机器人在应答。那么,该如何有效的拦截掉这些烦人的骚扰电话呢?小编以小米手机为例,一步一步把方法告诉你。打开拨号界面,左下角有个设置(三道横线),点击它进入设置界面,在设置界面,我们可以看到...

TCP/IP协议_大志。的博客-程序员宅基地

简介: 文章问个人学习的心得,仅供参考,不足之处请指出。TCP/IP协议是什么TCP/IP协议是一个面向连接的可靠的网络协议  面向连接:一个逻辑概念,它需要自己与目标主机进行三次握手来建立连接才能完成通信。创建连接完成也会进行资源的分配。  可靠的:连接时三次握手确认机制保证自己与目标主机的连接。四次分手机制来保证连接资源的释放。每次接收消息都会返回发送方ack确认包。什么是三次握手  这个图就表示三次握手的过程,我个人认为他就是为了保证可靠性而进行的一个测试,测试两台主机是否能接受对方.

全屏显示函数_元仙僧的博客-程序员宅基地

var runPrefixMethod = function (element, method) { var usablePrefixMethod; ["webkit", "moz", "ms", "o", ""].forEach(function (prefix) { if (usablePrefixMethod) return; if (prefix === "") {

android 设置画布颜色,Android更改画布背景颜色而不会丢失任何图纸_周周伦迷妹的博客-程序员宅基地

已经给出了你的问题的答案都指向了正确的方向:你需要在单独的图层中分离背景颜色块和前景图,然后合并它们,然后将它们全部保存在.png文件中.这就是Adobe Photoshop工作流程的设计……如果我们考虑它,它确实有意义:例如像MsPaint这样的软件:因为它不使用图层,它必须依赖于类似填充算法的东西完成(虽然以不完整的方式)远程类似于背景变化的东西……实现这种方法的一种方法是实例化由2个不同位图...

微信公众平台消息接口开发(1)启用接口_weixin_34378767的博客-程序员宅基地

微信公众平台 开发模式 消息接口微信 平台 消息 接口启用作者:http://txw1958.cnblogs.com/原文:http://www.cnblogs.com/txw1958/archive/2013/01/24/weixin-if1-enable.html微信公众平台开发入门教程请直接点击http://www.cnblogs.com/txw1958/p/w...

随便推点

网页服务器磁盘满了怎么办,Linux服务器磁盘满了怎么办_咣荀的博客-程序员宅基地

Linux服务器磁盘满了怎么办时间:2021-03-26 14:22:17来源:作者:在我们平常使用的开发或者测试环境,由于系统日志通常是debug级别,难免会碰到磁盘满的情况,这时候怎么办呢?01—查找大文件一般来说,我们的系统或者应用通常部署在/opt目录下,我们使用下面命令查找大文件:find /opt -type f -size +800M -print0 | xargs -0 d...

Spring底层核心原理解析_安和桥@write_boy的博客-程序员宅基地_spring底层原理

Spring底层核心原理解析Spring中是如何创建一个对象?Bean的创建过程推断构造方法AOP大致流程Spring事务本篇博客是对Spring的底层有一个整体的大致了解Bean的生命周期底层原理依赖注入底层原理初始化底层原理推断构造方法底层原理AOP底层原理Spring事务底层原理但都只是大致流程,后续会针对每个流程详细深入的讲解并分析源码实现。先来看看入门使用Spring的代码:ClassPathXmlApplicationContext context = new Cla

java同步读写,关于java:Collections中的synchronizedMap方法是否同步读写操作_小蓝是国王吖的博客-程序员宅基地

本问题已经有最佳答案,请猛点这里访问。当我做一个收藏.同步DMAP(Somehashmap)时,所有的都可以进入同步地图吗?还是只写同步操作?如果从地图上读到两条线怎么办?威尔是同步的吗?似乎有必要如果一个螺纹被放置()而另一个螺纹被放置(),该怎么办?因为Collections.synchronizedMap非常基本,几乎不能使用。还有用于更严重的并发使用的ConcurrentHashMap。看...

文件名文件内容批量替换工具_呈叙墨客的博客-程序员宅基地

软件名称:XCLNetFileReplace(文件名文件内容批量替换工具)版本:1.0发布日期:2013-12-29操作系统:windows(with .net framework 4.0)描述:本软件可以对文件名和内容进行批量替换,可选用正则表达式进行复杂的替换,支持Word/Excel/文本文件(无需安装office),同时也可以导出替换结果。安装说明:无需安装,可直接运行

【Java设计模式】单例模式与序列化_澡堂乐队主唱的博客-程序员宅基地_java 单例 序列化

序列化会破坏单例模式当使用双重校验锁并且使用了volatile的时候,这种看上去非常perfect的方式也可能存在单例模式被破坏的问题,那就是遇到序列化的时候。Q:序列化之后的对象还是同一个吗答案是 不是public class Singleton implements Serializable{ private volatile static Singleton singleton; private Singleton (){} public static Singleto

gen9 ws460c 惠普_HPE ProLiant WS460c Gen9 Graphics Server Blade中文版.pdf_周喆吾-Max的博客-程序员宅基地

HPE ProLiant WS460c Gen9| HPE ProLiant WS460c Gen9HPE ProLiant WS460cGPUHPE ProLiant WS460c Gen9• (VDI)• TM 1 IT(BYOD)E5-2600 v4 122,133 MHz HPE DDR4 (CAD)WebSmartMemor...

推荐文章

热门文章

相关标签