首页 > 代码库 > poj 3345(树形dp)

poj 3345(树形dp)

2024-07-03 01:25:54   236人阅读

题意：一个人要买通若干支持者，这些支持者的关系形成一棵森林，只要买通树根他的孩子节点也会被买通，问你至少要买通m个守卫要花多少钱。

思路：由于是一颗森林我们需要加一个结点使得他到每个点都建一条边，然后dp[i][j]表示i为根的结点买通j个需要的最小花费。

dp[v][j] = min(dp[v][j], dp[v][j-k] + dp[x][k]);

代码如下：

 1 #include <cstdio>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <set>
 6 #include <iostream>
 7 #include <queue>
 8 #include <map>
 9 #include <math.h>
10 #include <string>
11 #define MP(a, b) make_pair(a, b)
12 #define PB(a) push_back(a)
13 using namespace std;
14 
15 const int LEN = 210;
16 const int INF = 0x3f3f3f3f;
17 int n, m, vex[LEN], dp[LEN][LEN], ind[LEN], top;
18 vector<int> Map[LEN];
19 map<string, int> mp;
20 
21 int ch(string s){
22     if(!mp.count(s))mp[s] = top++;
23     return mp[s];
24 }
25 
26 int dfs(int v, int fa){
27     int ret = 1;
28     dp[v][0] = 0;
29     for(int i=0; i<Map[v].size(); i++){
30         int x = Map[v][i];
31         if(x != fa){ 
32             ret += dfs(x, v);
33             for(int j=n; j>=0; j--){
34                 for(int k=0; k<=j; k++){
35                     dp[v][j] = min(dp[v][j], dp[v][j-k] + dp[x][k]); 
36                 }
37             }
38         }
39     }
40     dp[v][ret] = min(dp[v][ret], vex[v]);
41     return ret;
42 }
43 
44 int main()
45 {
46     freopen("in.txt", "r", stdin);
47 
48     char buf[LEN], na[LEN], nb[LEN];
49     int tn, a, b;
50     while(scanf("%s", buf)!=EOF){
51         if(buf[0] == ‘#‘) break;
52         for(int i=0; i<LEN; i++) Map[i].clear();
53         memset(ind, 0, sizeof ind);
54         memset(dp, 0x3f, sizeof dp);
55         top = 1; mp.clear();vex[0] = INF;
56         sscanf(buf, "%d", &n);
57         scanf("%d", &m);
58         for(int i=0; i<n; i++){
59             scanf("%s%d", na, &tn);
60             a = ch(na); vex[a] = tn;
61             while(getchar() != ‘\n‘){
62                 scanf("%s", nb);
63                 b = ch(nb);
64                 ind[b] ++;
65                 Map[a].PB(b);
66                 Map[b].PB(a);
67             }
68         }
69         for(int i=1; i<=n; i++){
70             if(ind[i]) continue;
71             Map[0].PB(i);
72             Map[i].PB(0);
73         }
74         dfs(0, -1);
75         int ans = INF;
76         for(int i=m; i<=n; i++){
77             ans = min(ans, dp[0][i]);
78         }
79         printf("%d\n", ans);
80     }
81     return 0;
82 }
View Code

 


联系
我们