HDU 1054 Strategic Game (树形DP/匹配)

http://acm.hdu.edu.cn/showproblem.php?pid=1054

题意:

给你一棵树,n顶点,n-1条边,让你找到最少的顶点覆盖树上的所有边,即最小顶点覆盖

可以用匹配做(二分匹配的版题),也可以用树形DP

dp[s][0]表示以s为根的子树在s点不放的情况下的最小顶点数

dp[s][1]表示以s为根的子树在s点放的情况下的最小顶点数

则:

dp[s][0]=sigma(dp[ss][1])(ss表示s的子节点)(子节点必须放)

dp[s][1]=sigma(min(dp[ss][0],dp[ss][1]))(ss表示s的子节点)(子节点可放可不放)

则min(dp[0][0],dp[0][1])即为结果

HDU 1054 Strategic Game (树形DP/匹配)
  1 #pragma comment(linker, "/STACK:102400000,102400000")
  2 #include <cstdio>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <string>
  6 #include <cmath>
  7 #include <set>
  8 #include <list>
  9 #include <map>
 10 #include <iterator>
 11 #include <cstdlib>
 12 #include <vector>
 13 #include <queue>
 14 #include <stack>
 15 #include <algorithm>
 16 #include <functional>
 17 using namespace std;
 18 typedef long long LL;
 19 #define ROUND(x) round(x)
 20 #define FLOOR(x) floor(x)
 21 #define CEIL(x) ceil(x)
 22 const int maxn = 1510;
 23 const int maxm = 5010;
 24 const int inf = 0x3f3f3f3f;
 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL;
 26 const double INF = 1e30;
 27 const double eps = 1e-6;
 28 const int P[4] = {0, 0, -1, 1};
 29 const int Q[4] = {1, -1, 0, 0};
 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1};
 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1};
 32 
 33 int n;
 34 int dp[maxn][2];
 35 struct Edge
 36 {
 37     int u, v;
 38     int next;
 39 } edge[maxm];
 40 int en;
 41 int head[maxn];
 42 bool vis[maxn];
 43 void addsubedge(int u, int v)
 44 {
 45     edge[en].u = u;
 46     edge[en].v = v;
 47     edge[en].next = head[u];
 48     head[u] = en++;
 49 }
 50 void addedge(int u, int v)
 51 {
 52     addsubedge(u, v);
 53     addsubedge(v, u);
 54 }
 55 void init()
 56 {
 57     memset(head, -1, sizeof(head));
 58     memset(dp, 0x3f, sizeof(dp));
 59     en = 0;
 60     memset(vis, 0, sizeof(vis));
 61 }
 62 void input()
 63 {
 64     for (int i = 0; i < n; i++)
 65     {
 66         int u;
 67         int nx;
 68         scanf("%d:(%d)", &u, &nx);
 69         while (nx--)
 70         {
 71             int v;
 72             scanf("%d", &v);
 73             addedge(u, v);
 74         }
 75     }
 76 }
 77 void dfs(int s)
 78 {
 79     vis[s] = 1;
 80     dp[s][0] = 0;
 81     dp[s][1] = 1;
 82     for (int i = head[s]; i != -1; i = edge[i].next)
 83     {
 84         int v = edge[i].v;
 85         if (vis[v]) continue;
 86         dfs(v);
 87         dp[s][0] += dp[v][1];
 88         dp[s][1] += min(dp[v][0], dp[v][1]);
 89     }
 90 }
 91 void debug()
 92 {
 93     //
 94 }
 95 void solve()
 96 {
 97     dfs(0);
 98 }
 99 void output()
100 {
101     printf("%d\n", min(dp[0][0], dp[0][1]));
102 }
103 int main()
104 {
105     // std::ios_base::sync_with_stdio(false);
106 #ifndef ONLINE_JUDGE
107     freopen("in.cpp", "r", stdin);
108 #endif
109 
110     while (~scanf("%d", &n))
111     {
112         init();
113         input();
114         solve();
115         output();
116     }
117     return 0;
118 }
View Code

HDU 1054 Strategic Game (树形DP/匹配)

上一篇:[Leetcode]-- Swap Nodes in Pairs


下一篇:Convert Sorted Array to Binary Search Tree