BZOJ 3362 Navigation Nightmare 带权并查集
题目大意:给定一些点之间的位置关系,求两个点之间的曼哈顿距离
此题土豪题,不过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; else ans[queries[i].pos]=Distance(f[x]-f[y]); } for(i=1;i<=q;i++) printf("%d\n",ans[i]); }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。