hdu 1054 最小点集覆盖 || 树形dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1054

树形dp专辑：http://blog.csdn.net/xymscau/article/details/7561605

dp：对于每个节点都设两个状态，取或者不取

　　如果父节点不取，则所有儿子节点都得取，如果父节点要取，则儿子节点可以取、可以不取。

　　t为父节点，k为儿子节点：

   dp[t][0]+=dp[k][1];
   dp[t][1]+=min(dp[k][1],dp[k][0]);

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<vector>
 5 using namespace std;
 6 
 7 vector < int > Q[1505];
 8 int n, a,b,m,dp[1505][2],flag[1505],Min;
 9 
10 void dfs(int t)
11 {
12     flag[t]=1;
13     int s=( int )Q[t].size();
14     if(s==0)
15     {
16         dp[t][1]=1;
17         dp[t][0]=0;
18         return ;
19    //     cout << "^^^^   "<<t <<" "<<dp[t][1] << " "<<dp[t][0] <<endl;
20     }
21     dp[t][1]=1;
22     for(int i=0;i<s;i++)
23     {
24         int k=Q[t][i];
25         if(flag[k])  continue;
26         dfs(k);
27         dp[t][0]+=dp[k][1];
28         dp[t][1]+=min(dp[k][1],dp[k][0]);
29         // cout << t <<" "<<dp[t][1] <<"  "<<dp[t][0] <<endl;
30     }
31   //  cout <<"<<   "<< t <<" "<<dp[t][1] <<"  "<<dp[t][0] <<endl;
32 }
33 
34 int main( )
35 {
36     while(~scanf("%d",&n)){
37 
38         Min=0;
39         for(int i=0;i<n;i++)
40             Q[i].clear();
41         memset(flag,0,sizeof(flag));
42         memset(dp,0,sizeof(dp));
43         for(int i=0;i<n;i++)
44         {
45             scanf("%d:(%d)",&a,&m);
46             for(int j=1;j<=m;j++)
47             {
48                 scanf("%d",&b);
49                 Q[a].push_back(b);
50                 Q[b].push_back(a);
51             }
52         }
53 
54         for(int i=0;i<n;i++)
55         {
56             if((int)Q[i].size()!=0)
57             {
58                 dfs(i);
59                 Min=min(dp[i][1],dp[i][0]);
60                 break;
61             }
62         }
63 //                for(int i=0;i<=1;i++)
64 //        {            for(int j=0;j<n;j++)
65 //            printf("%d ",dp[j][i]);
66 //            printf("
");
67 //        }
68 
69         printf("%d
",Min);
70     }
71     return 0;
72 }

View Code

最小点集覆盖 = 最大匹配数

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<vector>
 5 using namespace std;
 6 
 7 vector < int > Q[1505];
 8 int n, a,b,m,sum,A[1505],B[1505];
 9 
10 bool getnum( int i)
11 {
12     for(int j=0;j<(int)Q[i].size();j++)
13     {
14         int k=Q[i][j];
15         if( A[k] ) continue;
16         A[k]=1;
17         if( B[k]==-1 || getnum( B[k] ) )
18         {
19             B[k]=i;
20             return true;
21         }
22     }
23     return false;
24 }
25 
26 int main( )
27 {
28     while(~scanf("%d",&n)){
29         sum=0;
30         for(int i=0;i<n;i++)
31             Q[i].clear();
32         for(int i=0;i<n;i++)
33         {
34             scanf("%d:(%d)",&a,&m);
35             for(int j=1;j<=m;j++)
36             {
37                 scanf("%d",&b);
38                 Q[a].push_back(b);
39                 Q[b].push_back(a);
40             }
41         }
42         memset(B,-1,sizeof(B));
43         for(int i=0;i<n;i++)
44         {
45             memset(A,0,sizeof(A));
46             if( getnum(i) ){
47                 //printf("& i= %d 
",i);
48                 sum++;
49             }
50 //            for(int i=0;i<n;i++)
51 //            printf("*%d ",B[i]);
52 //            cout<<endl;
53 
54         }
55         printf("%d
",sum/2);
56     }
57     return 0;
58 }

View Code