POJ 1984 Navigation Nightmare

Tag: 带权并查集

题目链接 | Here

题意

有$n$个网格状的农田,每个农田之间有距离,会依次给出关系,在给出关系后询问两个农田之间的曼哈顿距离是多少?若无法判断则输出-1

输入

!!多组案例输入!!

对于每组案例:
首先输入两个数字$n$和$m$,表示有$n$块农田,农田从1开始编号。
接下来$m$行,每行给出$a,b,l,d$,$a$和$b$表示农田的编号,$l$表示之间的距离,$d$表示$b$在$a$的$d$侧(只有四种,北-$N$,南-$S$,西-$W$,东-$E$)。
然后输入一个数字$k$,代表询问次数。
之后输入$k$行,每行有三个数字$a,b,c$,表示在$c$行后询问$a,b$间的曼哈顿距离是多少?

1
2
3
4
5
6
7
8
9
10
11
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6

输出

!!!多组输出,需要在每两组输出间空一行!!!

1
2
3
13
-1
10

题解

由于询问不是实时给出,所以显然需要离线处理。选取$N,E$作为正方向,接下来只要按照带权并查集,合并即可,由于是有两个参数,所以将$x,y$分开维护。

但是要注意在维护$x,y$需要同时维护,当维护$x$的差值时候,需要注意此时维护的$y$的差值为0,之后使用套用常规带权并查集即可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <algorithm>
#include <iostream>
#include <utility>
#include <map>
#include <vector>
using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define pbk push_back

typedef long long int ll;
const int maxn = 1e5+100;
int dsu[maxn],x[maxn],y[maxn];

map<int,vector<pair<int,int> > > qry;
pair<int,int> rela[maxn];
int wgt[maxn];
char dir[maxn];

void init(int n) { for(int i=0; i<=n; i++) dsu[i]=i; }
int find(int u) {
if(dsu[u] != u) {
int k = dsu[u];
dsu[u]=find(dsu[u]);
x[u]+=x[k]; y[u]+=y[k];
}
return dsu[u];
}
void mergeX(int a,int b,int k) {
int fa=find(a),fb=find(b);
dsu[fa]=fb;
x[fa] = k-x[a]+x[b];
y[fa] = -y[a]+y[b];
}
void mergeY(int a,int b,int k) {
int fa=find(a),fb=find(b);
dsu[fa]=fb;
y[fa] = k-y[a]+y[b];
x[fa] = -x[a]+x[b];
}
int query(int a,int b) {
int fa=find(a),fb=find(b);
if(fa!=fb) return -1;
return abs(x[a]-x[b])+abs(y[a]-y[b]);
}

int main() {
std::ios::sync_with_stdio(false);
int n,m,k;
int u,v,idx;
cin >> n >> m;
init(n);
for(int i=1; i<=m; i++) cin >> rela[i].fi >> rela[i].se >> wgt[i] >> dir[i];
cin >> k;
for(int i=0; i<k; i++) {
cin >> u >> v >> idx;
qry[idx].pbk(mkp(u,v));
}
for(int i=1; i<=m; i++) {
if(dir[i]=='W' || dir[i]=='E') {
if(dir[i]=='W') mergeX(rela[i].fi,rela[i].se,-wgt[i]);
else mergeX(rela[i].fi,rela[i].se,wgt[i]);
} else {
if(dir[i]=='S') mergeY(rela[i].fi,rela[i].se,-wgt[i]);
else mergeY(rela[i].fi,rela[i].se,wgt[i]);
}
if(!qry[i].empty()) {
int size=qry[i].size();
for(int j=0; j<size; j++) {
cout << query(qry[i][j].fi,qry[i][j].se) << endl;
}
}
}
return 0;
}


--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ