网站建设栏目添加/国内建站平台

题意：一个图中，只有上下左右四个方向的边。给出这样的一些边，求任意指定的2个节点之间的曼哈顿距离。查询时还有第三个参数k，表示只知道图中前k条边的信息时查询，此时如果不能确定，则输出-1。

思路：并查集。时时维护相对于并查集树顶结点的坐标偏移cx和cy两个数组。合并的时候仅仅更新树顶结点，其他结点在find操作时更新。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s))
#define N 40005
int f[N];
struct edge{int a,b,dx,dy;
}e[N];
struct question{int a,b,id,init;
}q[10005];
int n,m,qnum,res[10005],cx[N],cy[N];
int cmp(question x,question y){return x.id < y.id;
}
int find(int x){if(f[x] == x)return x;int tmp = f[x];f[x] = find(f[x]);cx[x] += cx[tmp];//每一次find操作，结点x都更新到其最新的坐标上cy[x] += cy[tmp];return f[x];
}
int main(){int i,j,c,xx,yy;char ori;scanf("%d %d",&n,&m);clr(cx, 0);clr(cy, 0);for(i = 1;i<=n;i++)f[i] = i;for(i = 1;i<=m;i++){scanf("%d %d %d %c",&e[i].a,&e[i].b,&c,&ori);e[i].dx = e[i].dy = 0;if(ori == 'E')e[i].dx = c;else if(ori == 'W')e[i].dx = -c;else if(ori == 'N')e[i].dy = c;elsee[i].dy = -c;}scanf("%d",&qnum);for(i = 1;i<=qnum;i++){scanf("%d %d %d",&q[i].a,&q[i].b,&q[i].id);q[i].init = i;}sort(q+1,q+qnum+1,cmp);for(i = j = 1;i<=qnum;i++){for(;j<=q[i].id;j++){xx = find(e[j].a);yy = find(e[j].b);if(xx == yy)//如果已经在一个区域了，那么他们的相对坐标是确定的，不用再次进行处理continue;f[yy] = xx;cx[yy] = cx[e[j].a]-cx[e[j].b]+e[j].dx;//只对yy所在集合的顶点结点进行处理，剩下的结点在进行find时处理cy[yy] = cy[e[j].a]-cy[e[j].b]+e[j].dy;}if(find(q[i].a) != find(q[i].b))res[q[i].init] = -1;elseres[q[i].init] = abs(cx[q[i].a]-cx[q[i].b])+abs(cy[q[i].a]-cy[q[i].b]);}for(i = 1;i<=qnum;i++)printf("%d\n",res[i]);return 0;
}