POJ1463 Strategic game (最小点覆盖 or 树dp)

给你一棵树形图，问最少多少个点覆盖所有的边。

可以用树形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])

 //dp

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = ;

 vector <int> G[N];

 int dp[N][];

 void dfs(int u, int p) {

     dp[u][] = , dp[u][] = ;

     for(int i = ; i < G[u].size(); ++i) {

         int v = G[u][i];

         if(v == p)

             continue;

         dfs(v, u);

         dp[u][] += dp[v][];

         dp[u][] += min(dp[v][], dp[v][]);

     }

 }

 int main()

 {

     int n;

     while(~scanf("%d", &n)) {

         int u, num, v;

         for(int i = ; i <= n; ++i) {

             scanf("%d:(%d)", &u, &num);

             while(num--) {

                 scanf("%d", &v);

                 G[u].push_back(v);

                 G[v].push_back(u);

             }

         }

         dfs(, -);

         printf("%d\n", min(dp[][], dp[][]));

         for(int i = ; i < n; ++i)

             G[i].clear();

     }

     return ;

 }

 /*

 13

 0:(3) 1 2 3

 1:(0)

 2:(2) 4 5

 3:(2) 6 7

 4:(0)

 5:(0)

 6:(2) 8 9

 7:(3) 10 11 12

 8:(0)

 9:(0)

 10:(0)

 11:(0)

 12:(0)

 */

边完全覆盖，也就是最小点覆盖所有边。

二分图中最大匹配=最小点覆盖

 //dp

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = ;

 vector <int> G[N];

 int dp[N][];

 void dfs(int u, int p) {

     dp[u][] = , dp[u][] = ;

     for(int i = ; i < G[u].size(); ++i) {

         int v = G[u][i];

         if(v == p)

             continue;

         dfs(v, u);

         dp[u][] += dp[v][];

         dp[u][] += min(dp[v][], dp[v][]);

     }

 }

 int main()

 {

     int n;

     while(~scanf("%d", &n)) {

         int u, num, v;

         for(int i = ; i <= n; ++i) {

             scanf("%d:(%d)", &u, &num);

             while(num--) {

                 scanf("%d", &v);

                 G[u].push_back(v);

                 G[v].push_back(u);

             }

         }

         dfs(, -);

         printf("%d\n", min(dp[][], dp[][]));

         for(int i = ; i < n; ++i)

             G[i].clear();

     }

     return ;

 }

 /*

 13

 0:(3) 1 2 3

 1:(0)

 2:(2) 4 5

 3:(2) 6 7

 4:(0)

 5:(0)

 6:(2) 8 9

 7:(3) 10 11 12

 8:(0)

 9:(0)

 10:(0)

 11:(0)

 12:(0)

 */

巴特西

POJ1463 Strategic game (最小点覆盖 or 树dp)

最新文章

热门文章