POJ-1984-Navigation Nightmare（向量并查集+离线）

题目链接：http://poj.org/problem?id=1984

好题！适合我这样的菜鸡思考和找自信

题目大意：给出n个节点，m条路径，对于每条路径，输入a，b（两节点），len（道路长度），dir（节点a到节点b是向东（E）西（W）南（S）北（N）四个方向）。k次询问，对于每次询问，给出a，b，c，点a到b在c时刻的曼哈顿距离。如果没有联通，输出-1.对于输入的m条路径，第i条是第i秒的时候出现的。

思路：一开始拿到这道题，想的是搜索，但是估算了一波时间复杂度，肯定不行，又想是不是树上操作，左右看半天发现不知道怎么写，突然想起了并查集，觉得可行，就写写试试。

由于有着方向，我就用两个变量NS，EW表示南北和东西两类方向，正数代表北||东，负数代表南||西。然后离线处理完所有的数据之后，开始查询。

用到了向量并查集的思想。画个图就很容易看了：（样例）

一开始是三个点之间的联通：

之后，再次读入一个点的时候讲之联通：观察就会发现，4到5节点=4到1节点+1到5节点。

然后将后面的读***通，即可然后读入后面的数据，刷新即可：

然后对于每次查询的时候，只用加加减减就好了：

ACCode：

// luogu-judger-enable-o2
//#pragma comment(linker, "/STACK:1024000000,1024000000")
 
#include<stdio.h>
#include<string.h>
#include<math.h>
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=4e4+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const int MOD=1e9+7;
const double EPS=1.0e-8;
const double PI=acos(-1.0);

struct Node1{
	int u,v,NS,EW,id;
	Node1(int _u=0,int _v=0,int _NS=0,int _EW=0,int _id=0){
		u=_u;v=_v;NS=_NS;EW=_EW;id=_id;
	}
};
struct Node2{
	int a,b,id,tim;
	Node2(int _a=0,int _b=0,int _id=0,int _tim=0){
		a=_a;b=_b;id=_id;tim=_tim;
	}
};
Node1 Edge[MAXN],F[MAXN<<1];
Node2 Ask[MAXN];
int Ans[MAXN];
int n,m;

void Debug(){
	for(int i=1;i<=n;++i){
		printf("%d vex : pre=%d EW=%d NS=%d\n",i,F[i].u,F[i].EW,F[i].NS);
	}
}
void Intt(){
	for(int i=1;i<=n;++i){
		F[i].u=i;F[i].EW=F[i].NS=0;
	}
}
int Find(int x){
	if(F[x].u==x) return x;
	int temp=F[x].u;
	F[x].u=Find(F[x].u);
	F[x].EW+=F[temp].EW;F[x].NS+=F[temp].NS;
	return F[x].u;
}
int Cmp(Node2 a,Node2 b){
	return a.tim<b.tim;
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		Intt();
		for(int i=1;i<=m;++i){
			int a,b,len;char c,h;
			scanf("%d%d%d%c%c",&a,&b,&len,&c,&h);
			if(h=='N'||h=='S'){
				if(h=='N') Edge[i]=Node1(a,b,len,0,i);
				else Edge[i]=Node1(a,b,-len,0,i);
			}
			else{
				if(h=='E') Edge[i]=Node1(a,b,0,len,i);
				else Edge[i]=Node1(a,b,0,-len,i);
			}
		}int k;scanf("%d",&k);
		for(int i=1;i<=k;++i){
			int a,b,id;scanf("%d%d%d",&a,&b,&id);
			Ask[i]=Node2(a,b,i,id);
		}sort(Ask+1,Ask+1+k,Cmp);
//		for(int i=1;i<=m;++i) printf("time=%d u:%d v=%d EW:%d NS:%d\n",i,Edge[i].u,Edge[i].v,Edge[i].EW,Edge[i].NS);
//		for(int i=1;i<=k;++i) printf("time=%d a=%d b=%d\n",Ask[i].tim,Ask[i].a,Ask[i].b);
		for(int i=1,j=1;1;){
//			cout<<"i,j: "<<i<<" "<<j<<endl;
			if(i==m+1||j==k+1){
				for(j;j<=k;++j) Ans[j]=-1;
				break;
			}
			if(i>=Ask[j].tim){
				int aa=Find(Edge[i].u),bb=Find(Edge[i].v);
				if(aa!=bb){
					F[aa].u=bb;
					F[aa].EW=F[Edge[i].v].EW+Edge[i].EW-F[Edge[i].u].EW;
					F[aa].NS=F[Edge[i].v].NS+Edge[i].NS-F[Edge[i].u].NS;
//					F[aa].EW=F[aa].EW+F[bb].EW+Edge[i].EW;
//					F[aa].NS=F[aa].NS+F[bb].NS+Edge[i].NS;
				}
				int Aska=Find(Ask[j].a),Askb=Find(Ask[j].b);
				if(Aska!=Askb) Ans[Ask[j].id]=-1;
				else{
//					cout<<Aska<<" "<<Askb<<endl;
					int res1=F[Ask[j].a].EW-F[Ask[j].b].EW;
					int res2=F[Ask[j].a].NS-F[Ask[j].b].NS;
//					cout<<"res1,res2: "<<res1<<" "<<res2<<endl;
					int ans=abs(res1)+abs(res2);
					Ans[Ask[j].id]=ans;
				}
//				cout<<"Ans is: "<<Ans[j]<<endl;
//				Debug();
				++j;
			}
			else{
				int aa=Find(Edge[i].u),bb=Find(Edge[i].v);
				if(aa!=bb){
					F[aa].u=bb;
					F[aa].EW=F[Edge[i].v].EW+Edge[i].EW-F[Edge[i].u].EW;
					F[aa].NS=F[Edge[i].v].NS+Edge[i].NS-F[Edge[i].u].NS;
//					F[aa].EW=F[Edge[i].v].EW+Edge[i].EW;
//					F[aa].NS=F[Edge[i].v].NS+Edge[i].NS;
				}
//				Debug();
				++i;
			}
		}
		for(int i=1;i<=k;++i) printf("%d\n",Ans[i]);
	}
}

/*

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6

*/