Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1984 Navigation Nightmare---并查集

Posted on 2010-08-02 19:12 Uriel 阅读(429) 评论(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<&& 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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理