bzoj1912: [Apio2010]patrol 巡逻【树形DP】

  • 内容
  • 评论
  • 相关

题目点击这里


首先这题给出了一棵树,然后要遍历所有的边并回到根,并且可以自行增加一到两条边(新加的边一定也要经过一次),求最小的路径。

这题题意有点容易弄错,一开始我以为是遍历所有的点就行了,然后加了一堆的判断,事实上那些都是没有必要的。。。

首先考虑k=0的情况(虽然没有k=0的数据),如果不加边,那么遍历路径的长度肯定是2(N-1),因为每条边都一定会经过两次。

那么k=1时,我们需要加一条边,首先想到对于树上的每一条路径,如果我们加一条边连接两条路径的端点,那么对于这条路径上的所有边我们都可以少走一次,然后因为我们加了一条边,所以要再多走一次,那么就会减少L-1的总路径长度,L为树上最长的路径,也就是树的直径。

然后就是k=2的情况,这回我们要找两条边,当然也是要找最长的。那么很可能出现找到的两条路径有交叉的情况,那么对于交叉部分的边来说我们在计算的时候减去了两次,所以我们到时候还要加回来重复的部分,但是这样找第二条边就要用不同的办法。我们可以把第一次找到最长的路径上的所有边的权值设为-1,然后再找,这样就可以解决问题。

所以说这题其实就是找两次树的直径,那么我用的是树形DP的方法。用f[i,1..4]表示以i为根节点的子树,最远点的距离、次远点的距离、最远点的编号、次远点的编号(记录编号是为了第二次DP时知道哪些边的长度为负数)。然后DP方程就懒得写出来了,我相信你们看程序是看得懂的。。。


代码:

var
  f:array[1..100000,1..4] of longint;
  v,next,a,fa,d:array[0..200000]of longint;
  b:array[1..100000]of boolean;
  n,m,i,j,k,ans,t,p,q:longint;
procedure adde(uu,vv:longint);
begin
  inc(k);
  v[k]:=vv;
  next[k]:=a[uu];
  a[uu]:=k;
  inc(k);
  v[k]:=uu;
  next[k]:=a[vv];
  a[vv]:=k;
end;
procedure dp(x,j:longint);
var
  i,k,w:longint;
begin
  i:=a[x];
  while i<>-1 do
  begin
    k:=v[i];
    if k<>j then
    begin
      fa[k]:=x;
      d[k]:=d[x]+1;
      dp(k,x);
      if b[k] and b[x] then w:=-1 else w:=1;
      if f[k,1]+w>f[x,1] then
      begin
        f[x,2]:=f[x,1];
        f[x,4]:=f[x,3];
        f[x,1]:=f[k,1]+w;
        f[x,3]:=f[k,3];
      end
      else if f[k,1]+w>f[x,2] then
      begin
        f[x,2]:=f[k,1]+w;
        f[x,4]:=f[k,3];
      end;
    end;
    i:=next[i];
  end;
  if f[x,3]=0 then f[x,3]:=x;
  if f[x,4]=0 then f[x,4]:=x;
end;
begin
  read(n,m);
  k:=-1;
  t:=(n-1) shl 1;
  fillchar(a,sizeof(a),255);
  for i:=1 to n-1 do
  begin
    read(p,q);
    adde(p,q);
  end;
  fillchar(b,sizeof(b),false);
  dp(1,0);
  for i:=1 to n do
  if f[i,1]+f[i,2]>ans then
  begin
    ans:=f[i,1]+f[i,2];
    p:=f[i,3];
    q:=f[i,4];
  end;
  t:=t-ans+1;
  if m=1 then
  begin
    writeln(t);
    exit;
  end;
  b[p]:=true;
  b[q]:=true;
  while d[p]>d[q] do
  begin
    p:=fa[p];
    b[p]:=true;
  end;
  while d[q]>d[p] do
  begin
    q:=fa[q];
    b[q]:=true;
  end;
  while p<>q do
  begin
    p:=fa[p];
    q:=fa[q];
    b[q]:=true;
    b[p]:=true;
  end;
  fillchar(f,sizeof(f),0);
  dp(1,0);
  ans:=0;
  for i:=1 to n do
  if f[i,1]+f[i,2]>ans then
  ans:=f[i,1]+f[i,2];
  writeln(t-ans+1);
end.

退役倒计时:18天

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据