注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj1984Navigation Nightmare题解  

2014-03-31 21:02:03|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                    导航
                                           BY   LGS
以下距离都为曼哈顿距离:
题目大意:给你N个点,M条边,一定是一颗树,每次只告诉相对于某一个点的位置和距离,求每秒所能知道任意两个点的位置

题解:并查集,当要查询的两个点不在同一个集合内,那输出-1,否则根据与父亲结点的距离。对于i和j之间的距离:就为ABS(X[I]-X[J]);Y也一样。至于每次合并由于不同的方向,要自己推出X,Y坐标变化,画个图吧。有一个并查集重点:当两个集合合并成一个集合,列入FA[A]=B;那么只需要更新A到B新的距离即可。至于A的叶节点的更新,则可以在要查询时再更新,更新写在get函数(找它爸爸的函数)里很方便,是递归更新的。

总结:并查集
代码:
  • Source Code
  • #include<cstdio>
    #include<algorithm>
    #define maxn 50000
    using namespace std;
    struct node{int q,p,t,id;}aa[maxn];
    int i,j,n,m,k,w,z,zz;
    int x[maxn],y[maxn],ans[maxn],fa[maxn],a[maxn],b[maxn],c[maxn];
    char u,pos[maxn];
    bool cmp(const node&a,const node&b){return a.t<b.t;}
    int abs(int a){return (a>0)?a:(-a);} 
    int find(int w)
     {
     if (fa[w]==w) return w;
     int tem=find(fa[w]);
     x[w]=x[w]+x[fa[w]];
     y[w]=y[w]+y[fa[w]];
     fa[w]=tem;
     return fa[w];
     }//并查集的更新
    void  po()
    {
    if (pos[j]=='N') {x[z]=-x[a[j]]+x[b[j]];y[z]=-y[a[j]]+c[j]+y[b[j]];}
    if (pos[j]=='S') {x[z]=-x[a[j]]+x[b[j]];y[z]=-y[a[j]]-c[j]+y[b[j]];}
    if (pos[j]=='W') {x[z]=-x[a[j]]-c[j]+x[b[j]];y[z]=-y[a[j]]+y[b[j]];}
    if (pos[j]=='E') {x[z]=-x[a[j]]+c[j]+x[b[j]];y[z]=-y[a[j]]+y[b[j]];} 
    }
    int main()
    {
     scanf("%d%d",&n,&m);
     for (i=1;i<=m;i++)
        {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        u=getchar();pos[i]=getchar();u=getchar();
        }
    scanf("%d",&k);
    for (i=1;i<=k;i++){scanf("%d%d%d",&aa[i].q,&aa[i].p,&aa[i].t);aa[i].id=i;}
    sort(aa+1,aa+k+1,cmp);
    for (i=1;i<=n;i++) fa[i]=i;
    w=0;u=0;
    for (i=1;i<=k;i++){
         for (j=w+1;j<=aa[i].t;j++){
                                   z=find(a[j]); zz=find(b[j]);
                                  if (z!=zz) {fa[z]=zz;po();}             
                                    }
          z=find(aa[i].q); zz=find(aa[i].p);
         if (z!=zz) ans[aa[i].id]=-1;
                   else ans[aa[i].id]=abs(x[aa[i].q]-x[aa[i].p])+abs(y[aa[i].q]-y[aa[i].p]);
                w=aa[i].t;                                                    
                       }
    for (i=1;i<=k;i++)printf("%d\n",ans[i]);
    return 0;
    } 

  评论这张
 
阅读(14)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018