|
|
Posted on 2010-08-02 19:12 Uriel 阅读(431) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 数据结构
题意：给出点数和边数 已知每一条边的起点终点编号和方向 几个Query，每个Query求两个编号的点在第 I 步之后的曼哈顿距离 思路：先将Query按操作步数的大小排序，从小到大 遍历每个操作，执行并集函数，然后如果这步有Query则对Query的两个点执行查集函数，如果在一个集合当中，他们的曼哈顿距离即为他们的父亲结点的曼哈顿距离，否则输出-1 并集函数写法：如果第x条边(第x 步操作产生的)两个端点不在同一集合，则合并，注意合并之后作为儿子的结点到父亲结点的曼哈顿距离要有变化，要分边的方向不同考虑，详见代码 查集函数注意x，y 相对距离的累加 这题G++始终过不了，开始以为是数组越界或是浮点误差，但是都排除了，还怀疑是abs()的问题，手写了ABS也不行。。有路过的大牛请不吝赐教~ 另外发现改手写ABS()之后从172MS降到125MS，很神奇~~ 代码如下：
 //Problem: 1984 User: Uriel
//Memory: 1352K Time: 125MS
//Language: C++ Result: Accepted
//Union-Find Set
//2010.08.02
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define MAXN 40010
#define ABS(x) ((x)>=0?(x):(-x))
  struct Edge {
 int a,b,w;
char dir;
 }e[MAXN];
struct query{
int idx,a,b;
}q[10010];
struct node{
int f,a,b;
}v[MAXN];
int n,m,k;
char d[4]={'N','E','S','W'};
int step[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int ex_dir(char c){
for(int i=0;i<4;i++)
if(d[i]==c)return i;
}
bool cmp(query a,query b){
return a.idx<b.idx;
}
int findset(int idx,int &x,int &y){
int t=idx;
x=y=0;
  while(v[t].f!=-1){
x+=v[t].a;
y+=v[t].b;
t=v[t].f;
 }
return t;
}
void unionset(int x){
int x1,x2,y1,y2;
int v1=e[x].a,v2=e[x].b;
int f1=findset(v1,x1,y1),f2=findset(v2,x2,y2);
if(f1==f2)return;
int dd=ex_dir(e[x].dir);
v[f2].f=f1;
v[f2].a=step[dd][0]*e[x].w+x1-x2;
v[f2].b=step[dd][1]*e[x].w+y1-y2;
}
int main(){
int i,j,f1,f2,x1,x2,y1,y2;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++){
scanf("%d %d %d %c",&e[i].a,&e[i].b,&e[i].w,&e[i].dir);
}
scanf("%d",&k);
for(i=0;i<k;i++){
scanf("%d %d %d",&q[i].a,&q[i].b,&q[i].idx);
}
sort(q,q+k,cmp);
for(i=0;i<=n;i++)v[i].f=-1;
for(i=0,j=0;i<m;i++){
unionset(i);
while(j<k && q[j].idx<=i+1){
f1=findset(q[j].a,x1,y1);
f2=findset(q[j].b,x2,y2);
if(f1==f2)printf("%d\n",ABS(x1-x2)+ABS(y1-y2));
else
printf("-1\n");
j++;
}
}
return 0;
}
|