HDU4003 树形DP

题意：给一棵n个节点的树, 节点编号为1~n, 每条边都有一个花费值.
有k个机器人从S点出发, 问让机器人遍历所有边,最少花费值多少?

这题最难的地方应该就是如何定义状态了

定义 $d p [u] [i]$

$d p [u] [i]$

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <iostream>
 8 #include <map>
 9 #include <stack>
10 #include <string>
11 #include <vector>
12 #define  pi acos(-1.0)
13 #define  eps 1e-6
14 #define  fi first
15 #define  se second
16 #define  rtl   rt<<1
17 #define  rtr   rt<<1|1
18 #define  bug         printf("******
")
19 #define  mem(a,b)    memset(a,b,sizeof(a))
20 #define  name2str(x) #x
21 #define  fuck(x)     cout<<#x" = "<<x<<endl
22 #define  f(a)        a*a
23 #define  sf(n)       scanf("%d", &n)
24 #define  sff(a,b)    scanf("%d %d", &a, &b)
25 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
26 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
27 #define  pf          printf
28 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
29 #define  FREE(i,a,b) for(i = a; i >= b; i--)
30 #define  FRL(i,a,b)  for(i = a; i < b; i++)+
31 #define  FRLL(i,a,b) for(i = a; i > b; i--)
32 #define  FIN         freopen("data.txt","r",stdin)
33 #define  gcd(a,b)    __gcd(a,b)
34 #define  lowbit(x)   x&-x
35 using namespace std;
36 typedef long long  LL;
37 typedef unsigned long long ULL;
38 const int mod = 1e9 + 7;
39 const int maxn = 2e5 + 10;
40 const int INF = 0x3f3f3f3f;
41 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
42 int n, s, k, tot, head[maxn], dp[maxn][15];
43 struct Edge {
44     int v, w, nxt;
45 } edge[maxn];
46 void init() {
47     tot = 0;
48     mem ( head, -1 );
49 }
50 void add ( int u, int v, int w ) {
51     edge[tot].v = v;
52     edge[tot].w = w;
53     edge[tot].nxt = head[u];
54     head[u] = tot++;
55 }
56 void dfs ( int u, int fa ) {
57     for ( int i = head[u]; ~i ; i = edge[i].nxt ) {
58         int v = edge[i].v, w = edge[i].w;
59         if ( v == fa ) continue;
60         dfs ( v, u );
61         for ( int i = k ; i >= 0 ; i-- ) {
62             dp[u][i] += dp[v][0] + 2 * w;
63             for ( int j = 1 ; j <= i ; j++ )
64                 dp[u][i] = min ( dp[u][i], dp[u][i - j] + dp[v][j] + j * w );
65         }
66     }
67 }
68 int main()  {
69     while ( ~sfff ( n, s, k ) ) {
70         init();
71         for ( int i = 1, u, v, w ; i < n ; i++ ) {
72             sfff ( u, v, w );
73             add ( u, v, w ), add ( v, u, w );
74         }
75         mem ( dp, 0 );
76         dfs ( s, -1 );
77         printf ( "%d
", dp[s][k] );
78     }
79     return 0;
80 }