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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1787/1832][AHOI2008]聚会  

2014-12-26 13:42:53|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1832: [AHOI2008]聚会

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 667  Solved: 229
[Submit][Status]

Description

Y 岛风景美丽宜人,气候温和,物产丰富。Y岛上有N个城市,有N-1条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是,小可可通过这些道路 可以走遍Y岛的所有城市。神奇的是,乘车经过每条道路所需要的费用都是一样的。小可可,小卡卡和小YY经常想聚会,每次聚会,他们都会选择一个城市,使得 3个人到达这个城市的总费用最小。 由于他们计划中还会有很多次聚会,每次都选择一个地点是很烦人的事情,所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处 的位置,希望你为他们的每一次聚会选择一个合适的地点。

Input

第 一行两个正整数,N和M。分别表示城市个数和聚会次数。后面有N-1行,每行用两个正整数A和B表示编号为A和编号为B的城市之间有一条路。城市的编号是 从1到N的。再后面有M行,每行用三个正整数表示一次聚会的情况:小可可所在的城市编号,小卡卡所在的城市编号以及小YY所在的城市编号。

Output

一共有M行,每行两个数Pos和Cost,用一个空格隔开。表示第i次聚会的地点选择在编号为Pos的城市,总共的费用是经过Cost条道路所花费的费用。

Sample Input

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Sample Output

5 2
2 5
4 1
6 0

数据范围:
100%的数据中,N<=500000,M<=500000。
40%的数据中N<=2000,M<=2000。

Solution

先预处理lca以及根到当前节点的路径长度d[]

对于每个询问,集合点只能在两两之间的lca上面

枚举lca吧233

Code


/**************************************************************
    Problem: 1832
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:5404 ms
    Memory:59400 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
const int MAXN=500010;
int n,m,x,y,z,d[MAXN],la[MAXN],et,Gt,q[MAXN*2],l,r,fa[MAXN][20];
struct E{int to,nxt,c;}e[MAXN<<1];
void add(int x,int y)
{
    e[++et]=(E){y,la[x]};la[x]=et;
    e[++et]=(E){x,la[y]};la[y]=et;
}
void newfa(int x)
{
    for(int i=1;fa[x][i-1];i++)
    fa[x][i]=fa[fa[x][i-1]][i-1];
}
void BFS()
{
    memset(d,127,sizeof(d));
    for(q[l=r=1]=1,d[1]=1;l<=r;l++)
    {
        for(int i=la[q[l]];i;i=e[i].nxt)
        if(d[e[i].to]>d[q[l]]+1)
        {
            d[e[i].to]=d[q[l]]+1;
            q[++r]=e[i].to;
            fa[e[i].to][0]=q[l];
            newfa(e[i].to);
        }
    }
}
int lca(int x,int y)
{
    if(d[x]<d[y]){int t=x;x=y;y=t;}
    int k=d[x]-d[y],cnt=0;
    while(k)
    {
        if(k&1)x=fa[x][cnt];
        cnt++;k>>=1;
    }
    if(x==y)return x;
    for(int i=19;i>=0;i--)
    if(fa[x][i]!=fa[y][i])
    {
        x=fa[x][i];y=fa[y][i];
    }
    return fa[x][0];
}
int dis(int x,int y,int l)
{
    return d[x]+d[y]-2*d[l];
}
int main()
{
    scanf("%d%d",&n,&m);int i,l1,l2,l3,l0,s1,s2,s3;
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    BFS();
    while(m--)
    {
        scanf("%d%d%d",&x,&y,&z);
        l1=lca(x,y);l0=lca(l1,z);
        s1=dis(x,l1,l1)+dis(y,l1,l1)+dis(z,l1,l0);
        l2=lca(x,z);
        s2=dis(x,l2,l2)+dis(y,l2,l0)+dis(z,l2,l2);
        l3=lca(y,z);
        s3=dis(x,l3,l0)+dis(y,l3,l3)+dis(z,l3,l3);
        if(s1<=s2&&s1<=s3)
        {
            printf("%d %d\n",l1,s1);
        }
        else if(s2<=s1&&s2<=s3)
        {
            printf("%d %d\n",l2,s2);
        }
        else
        {
            printf("%d %d\n",l3,s3);
        }
    }
}
  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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