(POJ - 1984) navigation nightare (weighted and search set)

Topic link ：1984 -- Navigation Nightmare

Chinese question meaning ：

Yes n A grid of farmland , There is a distance between each farmland , The relationship will be given in turn , After giving the relationship, ask what is the Manhattan distance between the two farms ？（ spot (x1,y1) Sum point (x2,y2) The Hamiltonian distance of is |x1-x2|+|y1-y2|）

If it cannot be judged, output -1.

This problem is solved by weighted union search , Whether the Hamiltonian distance of two points can be calculated depends on whether they have the same reference system , That is, whether they are in a set , We can determine the relative position of any two points in the set by the relationship between each point in the set and the representative elements of the set . Because this is a two-dimensional relationship , We can split it into two one-dimensional relationships , The final result is the combination .

For example, a set contains a,b,c……, The set represents the element is c, among a stay c West 3, Underside 5, and b stay c east 1, above 1, Then we can know a and b The Hamiltonian distance of is 4+6=10, And this problem is solved by using this idea , Now I'll mainly talk about how to perform and check the set and

 x and y In two different sets , Now I want to order x The representative element of the set is the representative element of the new set , Now know x To the east of its representative elements dx[x], and y To the east of its representative elements dx[y], And y stay x east wx, It is easy to know from the picture dx[f2]=dx[x]+wx-dx[y] Similarly, we can get the north-south direction of the merger , It should also be noted that the title does not indicate that the inquiry time is from small to large , So you need to add a sort , The analysis of the topic is basically finished , Now let's look at the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=40003;
int dx[N],dy[N],fu[N],n,m;
int a[N],b[N],l[N];
char op[N][5];
struct node{
	int u,v,t,id,ans;
}p[N];
bool cmp1(node a,node b)
{
	return a.t<b.t;
}
bool cmp2(node a,node b)
{
	return a.id<b.id;
}
void init()
{
	for(int i=1;i<=n;i++)
		fu[i]=i;
	memset(dx,0,sizeof dx);
	memset(dy,0,sizeof dy);
}
int find(int x)
{
	int t=fu[x];
	if(x==fu[x]) return x;
	fu[x]=find(fu[x]);
	dx[x]+=dx[t];
	dy[x]+=dy[t];
	return fu[x];
}
void merge(int x,int y,int wx,int wy)
{
	int f1=find(x),f2=find(y);
	fu[f2]=f1;
	dx[f2]=dx[x]+wx-dx[y];
	dy[f2]=dy[x]+wy-dy[y];
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		for(int i=1;i<=m;i++)
			scanf("%d%d%d%s",&a[i],&b[i],&l[i],op[i]);
		int k;
		scanf("%d",&k);
		for(int i=1;i<=k;i++)
			scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].t),p[i].id=i;
		sort(p+1,p+k+1,cmp1);
		int cnt=1;
		for(int i=1;i<=m;i++)
		{
			if(op[i][0]=='E') merge(a[i],b[i],l[i],0);
			else if(op[i][0]=='W') merge(a[i],b[i],-l[i],0);
			else if(op[i][0]=='N') merge(a[i],b[i],0,l[i]);
			else merge(a[i],b[i],0,-l[i]);
			while(p[cnt].t<=i&&cnt<=k)
			{
				int f1=find(p[cnt].u),f2=find(p[cnt].v);
				if(f1!=f2) p[cnt].ans=-1;
				else p[cnt].ans=abs(dx[p[cnt].u]-dx[p[cnt].v])+abs(dy[p[cnt].u]-dy[p[cnt].v]);
				cnt++;
			}
		}
		sort(p+1,p+k+1,cmp2);
		for(int i=1;i<=k;i++)
			printf("%d\n",p[i].ans);
	}
	return 0;
}