BZOJ 3362 POJ 1984 Navigation Nightmare 并与正确集中检查

BZOJ 3362 POJ 1984 Navigation Nightmare 并与正确集中检查

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

标题效果:一些养殖场是由一些南北或东西向的道路互连。

镶上在不断的过程中会问两个农场是什么曼哈顿的距离,假设现在是不是通信。那么输出-1。

思维:并与正确集中检查,f[i]点i至father[i]距离,为了维持两个值,一个是东西向的距离。一个是南北向的距离,由于以后更新的时候要用到。在合并的时候有些特殊。如今有一条边(x->y),设fx为x的根。fy为y的根,那么如今知道f到fx的距离。y到fy的距离。还知道x到y的距离,设fx到fy的距离为dis,则dis + f[y] = f[x] + edge[p].w,那么dis = f[x] – f[y] + edge[p].w。

依据这个公式来合并两个树就能够了。

CODE:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 40010
using namespace std;

struct Complex{
	int x,y,len;
	char c;
}edge[MAX];
struct Ask{
	int x,y;
	int pos,_id;
	bool operator <(const Ask &a)const {
		return pos < a.pos;
	}
}ask[MAX];
struct Status{
	int x,y;

	Status(int _,int __):x(_),y(__) {}
	Status() {}
	Status operator +(const Status &a)const {
		return Status(x + a.x,y + a.y);
	}
	Status operator -(const Status &a)const {
		return Status(x - a.x,y - a.y);
	}
}f[MAX];

int points,edges,asks;
int father[MAX];
int ans[MAX];

char s[10];

void Pretreatment();

int Find(int x);

int main()
{
	cin >> points >> edges;
	Pretreatment();
	for(int i = 1;i <= edges; ++i) {
		scanf("%d%d%d%s",&edge[i].x,&edge[i].y,&edge[i].len,s);
		edge[i].c = s[0];
	}
	cin >> asks;
	for(int i = 1;i <= asks; ++i)
		scanf("%d%d%d",&ask[i].x,&ask[i].y,&ask[i].pos),ask[i]._id = i;
	sort(ask + 1,ask + asks + 1);
	int now = 1;
	for(int i = 1;i <= edges; ++i) {
		int fx = Find(edge[i].x);
		int fy = Find(edge[i].y);
		if(fx != fy) {
			father[fy] = fx;
			Status temp;
			if(edge[i].c == 'N')	temp = Status(0,edge[i].len);
			if(edge[i].c == 'S')	temp = Status(0,-edge[i].len);
			if(edge[i].c == 'E')	temp = Status(edge[i].len,0);
			if(edge[i].c == 'W')	temp = Status(-edge[i].len,0);
			f[fy] = f[edge[i].x] - f[edge[i].y] + temp;
		}
		while(i >= ask[now].pos && now <= asks) {
			int fx = Find(ask[now].x);
			int fy = Find(ask[now].y);
			if(fx != fy)	ans[ask[now]._id] = -1;
			else {
				Status temp = f[ask[now].x] - f[ask[now].y];
				ans[ask[now]._id] = abs(temp.x) + abs(temp.y);
			}
			++now;
		}
	}
	for(int i = 1;i <= asks; ++i)
		printf("%d\n",ans[i]);
	return 0;
}

void Pretreatment()
{
	for(int i = 1;i <= points; ++i)
		father[i] = i;
}

int Find(int x)
{
	if(father[x] == x)	return x;
	int temp = father[x];
	father[x] = Find(father[x]);
	f[x] = f[x] + f[temp];
	return father[x];
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117342.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Root apk 2021_proguard混淆jar包

    Root apk 2021_proguard混淆jar包backdoor-apk从名字上我们就能知道它的用途了,没错就是用来制作APK后门的。这款工具使用起来非常方便,而且功能也很强大!话不多说,下面我们直接进入正题。首先,让我们对它进行安装,在安装前我们需要先安装它的一些依赖lib库文件:apt-getinstalllib32stdc++6lib32ncurses5lib32z1这里询问我们,对这些安装的服务,当他们更新时不再进行询…

  • 如何解决eclipse中的中文乱码问题[通俗易懂]

    eclipse中文乱码都是因为字符编码与默认的编码不符合导致的,有很多的方法可以解决,不需要安装任何插件就可以搞定。针对不同的情况,需要使用不同的方案,下面就针对一些案例讲解如何解决乱码问题。解决乱码问题的主要思路是设置正确合适的编码,如果不知道目标文件原本的编码,可以进行一定的尝试,通常尝试下GBK和UTF-8这两个编码即可。方法1设置单个文件的字符编码,解决单个文件的乱码问题有时候不小心cop…

  • linux命令行安装jenkins插件,Linux 安装Jenkins[通俗易懂]

    linux命令行安装jenkins插件,Linux 安装Jenkins[通俗易懂]图片.png图片.png1、上传下载的jenkins安装包图片.png2、执行安装命令sudorpm-ihjenkins-2.222.1-1.1.noarch.rpm图片.png自动安装完成之后会产生一下目录:/usr/lib/jenkins/jenkins.warWAR包/etc/sysconfig/jenkins配置文件/var/lib/jenkins/…

    2022年10月29日
  • uniapp 真机调试_app调试

    uniapp 真机调试_app调试一:华为手机实时调试APP代码基座流程1.打开手机的开发者模式,允许USB调试,手机操作流程,进入设置-关于手机,长按版本号(开启开发模式),然后按图操作,下拉屏幕发行已连接USB调试,手机端就暂时不用再操作了2.电脑安装360手机助手,这个软件打开浏览器或者用360软件助手下载就好了,它是HBuildX和手机连接的桥梁3.HBuildX操作运行之后就可以在控制台查看进展,会自动在手机安装APK调试基座(用于调试的APK,APK就是安卓APP的安装包).

  • 关于大学计算机相关专业学习路线的见解与分析

    关于大学计算机相关专业学习路线的见解与分析谨以此文献给仍然迷失在大学生活中的计算机专业学子!!!不管你是如何选择了这门专业,我想告诉你的是这是一个很深的领域,没有热爱不如尽早转行。根据百度百科计算机科学与技术专业(以下简称计算机专业)给出的描述,该专业的主干课程有算法、数据结构、操作系统、编译原理、计算机组成原理、计算机体系结构、计算机网络(划重点,这些都是专业基础课,其中的任意一门拿出来都够研究一生的,虽然大学的教育基本上都是讲…

  • 记一次没遇到过的UPX脱壳

    记一次没遇到过的UPX脱壳关于壳的介绍见CTF-WIKI这里就不多赘述了拿到我们的程序,先查看64位upx壳,首先直接upx-d试一下,结果是失败报错提示下图(一开始也有怀疑过是不是版本不兼容的问题,后来尝试高版本还是兼容低版本的)然后想尝试手脱,打开x64dbg,单步下去直接跑飞了,重新载入,想看看f7能否跟进,结果发现第一个指令是一个jmp指令,遂失败搜索这个报错无果,问了师傅,可能是upx非标准格式,找到了一篇文章链接如下:https://www.52pojie.cn/thread-326995-1-1.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号