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

n+e

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

 
 
 

日志

 
 

[BZOJ3743][Coci2015]Kamp  

2015-01-29 11:25:37|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3743: [Coci2015]Kamp

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 190  Solved: 95
[Submit][Status][Discuss]

Description

一颗树n个点,n-1条边,经过每条边都要花费一定的时间,任意两个点都是联通的。
有K个人(分布在K个不同的点)要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发,把这K个人分别送回去。
请你回答,对于i=1~n,如果在第i个点举行聚会,司机最少需要多少时间把K个人都送回家。

Input

第一行两个数,n,K。
接下来n-1行,每行三个数,x,y,z表示x到y之间有一条需要花费z时间的边。
接下来K行,每行一个数,表示K个人的分布。

Output

输出n个数,第i行的数表示:如果在第i个点举行聚会,司机需要的最少时间。

Sample Input

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

Sample Output

11 15 10 13 16 15 10

HINT

【数据规模】
K <= N <= 500000
1 <= x,y <= N, 1 <= z <= 1000000

Solution

不用各种DP的做法:

1. 将K个人所在的点集构成的一棵生成树求出来,并且找到生成树中的最长链

2. 假设司机送完最后一个人还要回到原点,那么司机在这棵树上必定走了两遍。

如果出发点在树的内部,那么ans=2*V,否则就是ans=2*(V+dis[这个点到树的最短距离])

3. 如果不回到原点的话,ans要扣掉从原点出发到树中的最远距离,不然不优。最远点一定是树中最长链的两个端点其中之一
所以三遍BFS就可以了

Code

/**************************************************************
    Problem: 3743
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2812 ms
    Memory:43212 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
inline int getc(){
    static char buf[1<<15],*S=buf,*T=buf;
    if(S==T)if(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)return 0;
    return*S++;
}int aa,ch;inline int F(){
    while(ch=getc(),ch<48||ch>57);aa=ch^48;
    while(ch=getc()^48,ch>=0&&ch<=9)aa=(aa<<3)+(aa<<1)+ch;return aa;
}char buf[1<<23],*O=buf,stk[30];int ts;void P(long long x){
    if(!x)*O++=48;else{
        for(ts=0;x;x/=10)stk[++ts]=x%10;
        for(;ts;*O++=48+stk[ts--]);
    }
    *O++='\n';
}
#define N 500010
int n,k,i,j,x,y,v,flower[N],q[N<<1],l,r,la[N],et=1,p[N];
long long ans,d0[N],d1[N],d[N];
bool in[N],vis[N];
struct E{int to,v,nxt;}e[N<<1];
#define add(x,y,v) (e[++et]=(E){y,v,la[x]},la[x]=et)
void bfs(int s,long long*d,int cas){int i;
    memset(vis,0,sizeof(vis));
    for(q[l=r=0]=s,vis[s]=1,d[s]=0;l<=r;l++)
    for(i=la[q[l]];i;i=e[i].nxt)
    if(!vis[e[i].to])
    {
        vis[q[++r]=e[i].to]=1,d[e[i].to]=d[q[l]]+e[i].v;
        if(cas)p[e[i].to]=i;
    }
}
#define max(a,b) (a>b?a:b)
int main(){
    for(n=F(),k=F(),i=1;i<n;i++)x=F(),y=F(),v=F(),add(x,y,v),add(y,x,v);
    for(i=l=1,r=0;i<=k;i++)flower[i]=F();
    /*mst*/
    bfs(flower[1],d0,1);memset(in,0,sizeof(in));
    for(in[flower[1]]=1,i=2;i<=k;i++)
    for(j=flower[i];!in[j]&&j!=flower[1];j=e[p[j]^1].to)
    ans+=e[p[j]].v,in[j]=1;
     
    memset(d,63,sizeof(d));
    memset(vis,0,sizeof(vis));
    for(l=1,r=0,i=1;i<=n;i++)if(in[i])d[q[++r]=i]=0,vis[i]=1;
    for(;l<=r;vis[q[l++]]=0)
    for(i=la[q[l]];i;i=e[i].nxt)if(d[e[i].to]>d[q[l]]+e[i].v)
    d[e[i].to]=d[q[l]]+e[i].v,!vis[e[i].to]?vis[q[++r]=e[i].to]=1:1;
     
    for(j=flower[1],i=2;i<=k;i++)if(d0[j]<d0[flower[i]])j=flower[i];
    for(bfs(j,d1,0),j=flower[1],i=2;i<=k;i++)if(d1[j]<d1[flower[i]])j=flower[i];
    for(bfs(j,d0,0),i=1,ans<<=1;i<=n;i++)
    if(!in[i])P(ans+(d[i]<<1)-max(d0[i],d1[i]));
    else P(ans-max(d0[i],d1[i]));
    *--O=0,puts(buf);
}
  评论这张
 
阅读(378)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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