题意:一棵有边权的树,树上有 k 个点,移动速度无穷大,而人速度为 1 ,点会尽量延时,而人要尽量快,问人从某点出发抓到所有点的最少时间。link

n,k50n,k\le 50

Solution

设 dp(u,v,tot,sum) 为警察正在从 u 到 v ,此时以 u 为根时 v 的子树中有 tot 名罪犯,而树上总共有 sum 名罪犯,这样的状态下警察抓到全局的所有罪犯的最短时间。

因为罪犯的速度是无穷大的,所以 v 子树中的罪犯可以在整棵 v 的子树中自由分配。罪犯自然是要使得时间尽量延长的,那么 dp 值就应该是所有分配方案中时间的最大值,而对于一个确定了的分配方案,警察自然会选择耗时最短的移动方式,所以方案的时间就应该是所有移动方式中时间的最小值。

于是考虑如何把 tot 名罪犯分配到 v 的不同子树中,并依次考虑对于这些情况警察先往第几棵子树的方向走会更优。

注意一旦决定往一个方向去走了,在碰到叶子结点之前是不会回头的。

最直接的想法是对每棵子树考虑子树内有几名罪犯,再强制让警察往它的方向走,计算出直到抓完全局所有罪犯的最少耗时,在这些耗时中取最大的一种。但是这么设显然有 bug ,因为警察是自由的,他不一定会往你期待的那个方向走。这些子树内罪犯分布的状态,是会互相影响的。

可以用背包解决这个问题。设 bag(i,j) 表示当前在 v 的前 i 棵子树中总共分配了 j 名罪犯时,警察只能往前 i 棵子树走,以最优策略抓到全局所有罪犯的最长耗时。设第 i 棵子树根结点编号为 k ,考虑往第这棵子树放几个罪犯,再考虑这时警察是否会选择第一步往 k 的方向走,有转移式:

bag(i,j)=maxr=1j{min{bag(i1,jr),wj,k+dp(j,k,r,tot)}}bag(i,j)=\max_{r=1}^{j} \lbrace \min \lbrace bag(i-1,j-r),w_{j,k}+dp(j,k,r,tot ) \rbrace \rbrace

bag(0,0) 初始化为 inf 。

因为警察下一步一定会往 v 某个子树的方向去走,而且这样一来对每个第 i 棵子树都考虑了它与第 [1,i-1] 棵子树内罪犯的分布状况对警察如何抉择移动方案的双向影响,综合起来看,最后得到的结果就可以说是考虑周到的了。

碰到叶子之前不会回头,而一到叶子 sum 就会减少,所以可以记忆s化搜索,不会死循环。

边界是 sum=0 或者当前到了叶子结点,而叶子结点又要讨论 tot 与 sum 是否相等,从而判断要返回还是直接停在当前点。

Reflection

罪犯和警察在博弈的感觉。

关于状态转移式,这里的解释比较不自然,应该有更加巧妙的理解。

不过用做背包的方法来解决状态之间相互影响的问题本身就已经十分有趣了。

另外,在递归函数内定义变量,一定一定要初始化。

Code

link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//Have a nice day:)
#include<bits/stdc++.h>
using namespace std;
#define LL long long

inline int read();

const int maxn=50+2;
const int inf=2147483647;

int n, m, c, s, tim;
bool leaf[maxn];
int he[maxn], ne[maxn<<1], to[maxn<<1], w[maxn<<1];
int siz[maxn], dp[maxn][maxn][maxn];

void Add_Edge(int x, int y, int z)
{
ne[++c]=he[x]; he[x]=c; to[c]=y; w[c]=z;
ne[++c]=he[y]; he[y]=c; to[c]=x; w[c]=z;
}

void Get_Size(int p, int f)
{
int cnt=0;
for(int i=he[p]; i; i=ne[i])
{
++cnt;
if(to[i]==f) continue;
Get_Size(to[i], p);
siz[p]+=siz[to[i]];
}
if(cnt==1) leaf[p]=1;
}

int Search(int p, int front, int tot)
{
if(!tot) return 0;
if(dp[p][front][tot]!=-1) return dp[p][front][tot];
if(leaf[to[p]])
{
if(front==tot) return 0;
dp[p][front][tot]=Search(p^1, tot-front, tot-front)+w[p];
return dp[p][front][tot];
}

int bag[maxn][maxn], cnt=0;

for(int i=1; i<=front; ++i) bag[0][i]=0;
bag[0][0]=inf;
for(int i=he[to[p]]; i; i=ne[i])
{
if((i^1)==p) continue;
++cnt;
for(int j=front; j>=0; --j)
{
bag[cnt][j]=bag[cnt-1][j];
for(int k=j; k>=1; --k)
{
bag[cnt][j]=max(bag[cnt][j],
min(bag[cnt-1][j-k], w[i]+Search(i, k, tot)));
}
}
}

return dp[p][front][tot]=bag[cnt][front];
}

void Work()
{
memset(dp, -1, sizeof(dp));

n=read(); c=1;
for(int i=1; i<n; ++i)
{
int x=read(), y=read(), z=read();
Add_Edge(x, y, z);
}
s=read(); m=read();
for(int i=1; i<=m; ++i) ++siz[read()];

Get_Size(s, 0);

tim=inf;
for(int i=he[s]; i; i=ne[i])
{
tim=min(tim, w[i]+Search(i, siz[to[i]], m));
}

printf("%d", tim);
}

int main()
{
//freopen("868e.in","r",stdin);
//freopen("868e.out","w",stdout);

Work();

return 0;
}

inline int read()
{
char c; bool type=1;
while((c=getchar())<'0' || c>'9')
if(c=='-') type=0;
int ans=c^48;
while((c=getchar())>='0' && c<='9')
ans=(ans<<3)+(ans<<1)+(c^48);
return type?ans:-ans;
}