pku1848 Tree

http://poj.org/problem?id=1848

DP, 树状DP

一个节点形成环的过程中只有3种状态，

0：有0条边连着这个点

1：有1条边连着这个点

2：有2条边连着这个点

转移还可以再优化，不过不太好写，直接上3层循环。。。

代码中inf的定义：至少要添无穷多个边，才可以满足要求 ---等价于---> 添多少都没用

  1 #include <stdio.h>
  2 #include <vector>
  3 #define N 123
  4 
  5 using namespace std;
  6 
  7 vector<int> a[N];
  8 int mark[N], dp[N][3];
  9 const int inf = 1234;
 10 
 11 int min(int x, int y)
 12 {
 13     return x<y? x: y;
 14 }
 15 
 16 int limit_inf(int x)
 17 {
 18     return x>inf? inf: x;
 19 }
 20 
 21 int f(int x, vector<int> b)
 22 {
 23     int i, j, k, sum1, min1;
 24     
 25     //0
 26     sum1 = 0;
 27     for(i=0; i<b.size(); i++)
 28     {
 29         sum1 += dp[b[i]][2];
 30     }
 31     dp[x][0] = limit_inf(sum1);
 32 
 33     //1
 34     min1 = inf;
 35     for(i=0; i<b.size(); i++)
 36     {
 37         sum1 = min(dp[b[i]][0], dp[b[i]][1]);
 38         for(j=0; j<b.size(); j++)
 39         {
 40             if(j != i)
 41             {
 42                 sum1 += dp[b[j]][2];
 43             }
 44         }
 45         min1 = min(min1, sum1);
 46     }
 47     dp[x][1] = limit_inf(min1);
 48 
 49     //2
 50     min1 = inf;
 51     for(i=0; i<b.size(); i++)
 52     {
 53         for(j=0; j<b.size(); j++)
 54         {
 55             if(j != i)
 56             {
 57                 sum1 = min(dp[b[i]][0], dp[b[i]][1]) + 1;
 58                 sum1 += min(dp[b[j]][0], dp[b[j]][1]);
 59                 for(k=0; k<b.size(); k++)
 60                 {
 61                     if((k != i) && (k != j))
 62                     {
 63                         sum1 += dp[b[k]][2];
 64                     }
 65                 }
 66                 min1 = min(min1, sum1);
 67             }
 68         }
 69     }
 70     for(i=0; i<b.size(); i++)
 71     {
 72         sum1 = dp[b[i]][1] + 1;
 73         for(j=0; j<b.size(); j++)
 74         {
 75             if(j != i)
 76             {
 77                 sum1 += dp[b[j]][2];
 78             }
 79         }
 80         min1 = min(min1, sum1);
 81     }
 82     dp[x][2] = limit_inf(min1);
 83     return 0;
 84 }
 85 
 86 int dfs(int x)
 87 {
 88     int i, j;
 89     vector<int> b;
 90     b.clear();
 91     //printf("(%d: ", x);
 92     for(i=0; i<a[x].size(); i++) 
 93     {
 94         j = a[x][i];
 95         if(mark[j] == 0)
 96         {
 97             b.push_back(j);
 98             mark[j] = 1;
 99             dfs(j);
100         }
101     }
102     //printf(" ) ");
103     return f(x, b);
104 }
105 
106 int main()
107 {
108     int n, i, x, y;
109     while(~scanf("%d", &n))
110     {
111         for(i=1; i<=n; i++)
112         {
113             dp[i][0] = dp[i][1] = dp[1][2] = inf;
114             mark[i] = 0;
115             a[i].clear();
116         }
117         for(i=1; i<=n-1; i++)
118         {
119             scanf("%d%d", &x, &y);
120             a[x].push_back(y);
121             a[y].push_back(x);
122         }
123         mark[1] = 1;
124         dfs(1);
125         if(dp[1][2] == inf)
126         {
127             dp[1][2] = -1;
128         }
129         printf("%d\n", dp[1][2]);
130         /*
131         for(i=1; i<=n; i++)
132         {
133             printf("%5d %5d %5d\n", dp[i][0], dp[i][1], dp[i][2]);
134         }
135         */
136     }
137     return 0;
138 }