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天
发表回复