LA 2038 最少点覆盖

题目链接：https://vjudge.net/problem/UVALive-2038

题意：我看了原题，lrj的书上题意写错了，应该是最少点覆盖，当然可以用最大匹配去做，由于是树形的；

可以树形DP；

d[u][0] : u 结点 不放；

d[u][1] : u 结点放；

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;

 int n;

 vector<int> G[maxn];

 int d[maxn][];

 int p[maxn];

 int dfs(int u,int fa) {

     int d = G[u].size();

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

     {

         int v = G[u][i];

         if(v!=fa)

             dfs(v,p[v]=u);

     }

 }

 int dp(int cur,int f,int pa) {

     if(d[cur][f]>)

         return d[cur][f];

     if(f==) {

         d[cur][f] = ;

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

             int v = G[cur][i];

             if(v!=pa)

             d[cur][f] +=min(dp(v,,cur),dp(v,,cur));

         }

     }

     else {

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

             int v = G[cur][i];

             if(v!=pa)

                 d[cur][f] +=dp(v,,cur);

         }

     }

     return d[cur][f];

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF) {

         memset(d,,sizeof(d));

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

             G[i].clear();

         int u,v,num;

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

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

             for(int j=;j<num;j++) {

                 scanf("%d",&v);

                 G[u].push_back(v);

                 G[v].push_back(u);

             }

         }

         p[] = -;

         dfs(,-);

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

     }

     return ;

 }