首页 > 代码库 > POJ1463 Strategic game (最小点覆盖 or 树dp)
POJ1463 Strategic game (最小点覆盖 or 树dp)
题目链接：http://poj.org/problem?id=1463
给你一棵树形图，问最少多少个点覆盖所有的边。
可以用树形dp做，任选一点，自底向上回溯更新。
dp[i][0] 表示不选i点 覆盖子树所有边的最少点个数，那选i点的话，那么i的邻接节点都是必选的，所以dp[i][0] += dp[i.son][1]
dp[i][1] 表示选i点 覆盖子树所有边的最少点个数，那么i的邻接点可选可不选(而不是一定不选，看注释样例就知道了)，所以dp[i][0] += min(dp[i.son][1], dp[i.son][0])
1 //dp 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1505;17 vector <int> G[N];18 int dp[N][2];19 20 void dfs(int u, int p) {21 dp[u][0] = 0, dp[u][1] = 1;22 for(int i = 0; i < G[u].size(); ++i) {23 int v = G[u][i];24 if(v == p)25 continue;26 dfs(v, u);27 dp[u][0] += dp[v][1];28 dp[u][1] += min(dp[v][0], dp[v][1]);29 }30 }31 32 int main()33 {34 int n;35 while(~scanf("%d", &n)) {36 int u, num, v;37 for(int i = 1; i <= n; ++i) {38 scanf("%d:(%d)", &u, &num);39 while(num--) {40 scanf("%d", &v);41 G[u].push_back(v);42 G[v].push_back(u);43 }44 }45 dfs(0, -1);46 printf("%d\n", min(dp[0][0], dp[0][1]));47 for(int i = 0; i < n; ++i)48 G[i].clear();49 }50 return 0;51 }52 /*53 1354 0:(3) 1 2 355 1:(0) 56 2:(2) 4 557 3:(2) 6 758 4:(0) 59 5:(0) 60 6:(2) 8 961 7:(3) 10 11 1262 8:(0) 63 9:(0) 64 10:(0) 65 11:(0) 66 12:(0) 67 */
边完全覆盖，也就是最小点覆盖所有边。
二分图中最大匹配=最小点覆盖
1 //dp 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1505;17 vector <int> G[N];18 int dp[N][2];19 20 void dfs(int u, int p) {21 dp[u][0] = 0, dp[u][1] = 1;22 for(int i = 0; i < G[u].size(); ++i) {23 int v = G[u][i];24 if(v == p)25 continue;26 dfs(v, u);27 dp[u][0] += dp[v][1];28 dp[u][1] += min(dp[v][0], dp[v][1]);29 }30 }31 32 int main()33 {34 int n;35 while(~scanf("%d", &n)) {36 int u, num, v;37 for(int i = 1; i <= n; ++i) {38 scanf("%d:(%d)", &u, &num);39 while(num--) {40 scanf("%d", &v);41 G[u].push_back(v);42 G[v].push_back(u);43 }44 }45 dfs(0, -1);46 printf("%d\n", min(dp[0][0], dp[0][1]));47 for(int i = 0; i < n; ++i)48 G[i].clear();49 }50 return 0;51 }52 /*53 1354 0:(3) 1 2 355 1:(0) 56 2:(2) 4 557 3:(2) 6 758 4:(0) 59 5:(0) 60 6:(2) 8 961 7:(3) 10 11 1262 8:(0) 63 9:(0) 64 10:(0) 65 11:(0) 66 12:(0) 67 */
POJ1463 Strategic game (最小点覆盖 or 树dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。