題目大意：給定一些點之間的位置關系，求兩個點之間的曼哈頓距離

此題土豪題。只是POJ也有一道相同的題，能夠刷一下

別被題目坑到了，這題不強制在線。把詢問離線處理就可以

然后就是帶權并查集的問題了。。

。

將權值設為方向向量，重載+和-，依照正常權值并查集做即可了

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 40400 using namespace std; struct abcd{int x,y;abcd(){}abcd(int X,int Y):x(X),y(Y){}abcd operator + (const abcd &Y) const{return abcd( x+Y.x , y+Y.y );}abcd operator - (const abcd &Y) const{return abcd( x-Y.x , y-Y.y );} }f[M]; struct operation{int x,y;abcd temp; }operations[M]; struct query{int x,y,z,pos;bool operator < (const query &Y) const{return z < Y.z ;} }queries[10100]; int n,m,q,fa[M],ans[10100]; int Distance(abcd x) {return abs(x.x)+abs(x.y); } int Find(int x) {if(!fa[x]||fa[x]==x)return fa[x]=x;int y=fa[x];fa[x]=Find(fa[x]);f[x]=f[y]+f[x];return fa[x]; } int main() {int i,j,x,y,z;char p[10];cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d%d%s",&operations[i].x,&operations[i].y,&z,p);switch(p[0]){case 'E':operations[i].temp=abcd(z,0);break;case 'W':operations[i].temp=abcd(-z,0);break;case 'N':operations[i].temp=abcd(0,z);break;case 'S':operations[i].temp=abcd(0,-z);break;}}cin>>q;for(i=1;i<=q;i++)scanf("%d%d%d",&queries[i].x,&queries[i].y,&queries[i].z),queries[i].pos=i;sort(queries+1,queries+q+1);for(i=1,j=1;i<=q;i++){for(;j<=queries[i].z;j++){int x=operations[j].x;int y=operations[j].y;int fx=Find(x),fy=Find(y);fa[fy]=fx;f[fy]=f[x]-f[y]+operations[j].temp;}int x=queries[i].x;int y=queries[i].y;if( Find(x)!=Find(y) )ans[queries[i].pos]=-1;elseans[queries[i].pos]=Distance(f[x]-f[y]);}for(i=1;i<=q;i++)printf("%d\n",ans[i]); }

轉載于:https://www.cnblogs.com/lxjshuju/p/6791500.html

總結

以上是生活随笔為你收集整理的BZOJ 3362 Navigation Nightmare 带权并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。