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])即为结果
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 }