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

n+e

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

 
 
 

日志

 
 

[BZOJ1912][Apio2010]patrol 巡逻  

2014-12-01 19:56:10|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1912: [Apio2010]patrol 巡逻

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 500  Solved: 291
[Submit][Status]

Description

[BZOJ1912][Apio2010]patrol 巡逻 - Trinkle - n+e

Input

第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行,每行两个整数 a, b, 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。

Output

输出一个整数,表示新建了K 条道路后能达到的最小巡逻距离。

Sample Input

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

Sample Output

11

HINT

10%的数据中,n ≤ 1000, K = 1;
30%的数据中,K = 1;
80%的数据中,每个村庄相邻的村庄数不超过 25;
90%的数据中,每个村庄相邻的村庄数不超过 150;
100%的数据中,3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

Solution

k=1:求最长链

k=2:最长链求完把链上的边权设为-1,再做一次最长链。

注意一下第一次时要用bfs,因为要找到头和尾;第二次时只能用dfs,因为如果bfs的话第一遍出来的不一定是最长链的端点(因为有负数在里面)。

貌似还有奇怪的dp做法不明觉厉。。。

Code

/**************************************************************
    Problem: 1912
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:728 ms
    Memory:6944 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 100010
int n,k,i,j,x,y,ans,tmp,id,et=1,la[N],d[N],p[N],q[N<<2],l,r;bool in[N];
struct E{int to,v,nxt;}e[N<<1];
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define add(x,y) (e[++et]=(E){y,1,la[x]},la[x]=et)
int bfs(int s)
{
    tmp=id=1<<31;int i;memset(d,63,sizeof(d));
    for(q[l=r=0]=s,in[s]=1,d[s]=0,p[s]=-1;l<=r;in[q[l++]]=0)
    for(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,p[e[i].to]=i,
    d[e[i].to]>tmp?tmp=d[e[i].to],id=e[i].to:1,
    !in[e[i].to]?in[q[++r]=e[i].to]=1:1;
    return id;
}
void dfs(int x)
{
    int i,fst=0,sec=0;d[x]=0,in[x]=1;
    for(i=la[x];i;i=e[i].nxt)
    !in[e[i].to]?dfs(e[i].to),
    d[e[i].to]+e[i].v>=fst?sec=fst,fst=d[e[i].to]+e[i].v:
    d[e[i].to]+e[i].v>sec?sec=d[e[i].to]+e[i].v:1:1;
    tmp<fst+sec?tmp=fst+sec:1,d[x]=fst;
}
int main()
{
    for(n=F(),k=F(),i=1;i<n;i++)x=F(),y=F(),add(x,y),add(y,x);
    ans=(n-1)<<1,bfs(bfs(1)),ans-=tmp-1;
    if(k==1)return printf("%d",ans),0;
    for(i=id;p[i]!=-1;i=e[p[i]^1].to)e[p[i]].v=e[p[i]^1].v=-1;
    memset(d,63,sizeof(d)),tmp=1<<31,dfs(1),printf("%d",ans-tmp+1);
}
  评论这张
 
阅读(189)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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