POJ 1984 Navigation Nightmare（带权并查集）

POJ 1984 Navigation Nightmare（带权并查集）

​​传送门​​

题目大意

有多个点，在平面上位于坐标点上，给出一些关系，表示某个点在某个点的正东/西/南/北方向多少距离，然后给出一系列询问，表示在第几个关系给出后询问某两点的曼哈顿距离，或者未知则输出-1。

思路

op用来表示方向，东南为正方向 如果是南北，改的是x轴，东西改的是y轴

代码

int fa[maxn];int disx[maxn],disy[maxn];int n,m;struct node{ int x; int y; int v; char dic[10];//方向 }str[maxn];int find(int x){ if(fa[x]==x){ return x; } int tmp=find(fa[x]); disx[x]+=disx[fa[x]]; disy[x]+=disy[fa[x]]; return fa[x]=tmp;}void Union(node str){ int op=0; int x=str.x,y=str.y; if(str.dic[0]=='S'||str.dic[0]=='E') op=1;//东南位正 else op=-1; int fx=find(x),fy=find(y); if(str.dic[0]=='S'||str.dic[0]=='N'){//上下，改的是y if(fx!=fy){ fa[fx]=fy; disx[fx]=disx[y]-disx[x]+str.v*op; disy[fx]=disy[y]-disy[x]; } } else{ if(fx!=fy){ fa[fx]=fy; disy[fx]=disy[y]-disy[x]+str.v*op; disx[fx]=disx[y]-disx[x]; } }}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ fa[i]=i; } for(int i=1;i<=m;i++){ scanf("%d%d%d%s",&str[i].x,&str[i].y,&str[i].v,str[i].dic); } int t; scanf("%d",&t); int now=1; for(int i=1;i<=t;i++){ int a,b,suoyin; scanf("%d%d%d",&a,&b,&suoyin); while(now<=suoyin){ Union(str[now++]); } int fx=find(a); int fy=find(b); if(fx!=fy){ puts("-1"); } else{ int tmp=abs(disx[a]-disx[b])+abs(disy[a]-disy[b]); printf("%d\n",tmp); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。