|
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; }
|