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; }
|