大家好，又见面了，我是全栈君，今天给大家准备了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];
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117342.html原文链接：https://javaforall.net
