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
|
输出
!!!多组输出，需要在每两组输出间空一行!!!
题解
由于询问不是实时给出，所以显然需要离线处理。选取$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;
}
|
