UVa 1218 Perfect Service dp：树上dp 状态转移方程的优化

UVa 1218 Perfect Service 树上dp 状态转移方程的优化

The question is from here.

与这个题目 UVa 1220 Party at Hali-Bula dp：树的最大独立集写法很像，虽然各有不同；

My Solution

状态定义：d[u][0] 表示u是服务器，每个子结点可以是服务器也可以不是；

                  d[u][1] 表示u不是服务器，但u的父亲是服务器，所有子节点不是服务器，不然一个非服务器要连2个服务器了，illegal；

                  d[u][2] 表示u不是服务器， u的父亲不是服务器，则必须有一个子结点是服务器

//warming : 这样定义root的时候怎么第1种或者第3种；leaves必须为第1种或第2种；

状态转移：d[u][0] = sum{min(d[v][0], d[v][1])} +1;

                  d[u][1] = sum(d[v, 2));

                  d[u][2]是指只有一个son是服务器，所以用 d[u][1] - d[v][2] +d[v][0] 娶妻最小值;

边界：         d[u][0] = 1;d[u][1] = 0;d[u][2] = maxn;后面不存在的d[u][1]也会在处理之后变成maxn；              

#include 
#include 
#include 
//#define LOCAL
using namespace std;
const int maxn = 10008;
vector sons[maxn],G[maxn];
int d[maxn][3],p[maxn],n;

inline void read_tree()
{
    int u,v;
    for(int i = 0; i < n-1; i++){
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

void dfs(int u, int fa)
{
    int d = G[u].size();
    for(int i = 0; i < d; i++){
        int v = G[u][i];
        if(v != fa) dfs(v, p[v] = u);
    }
}

void dp(int u)
{
    d[u][0] = 1;d[u][1] = 0;d[u][2] = maxn;         //setting the edge
    int sz = sons[u].size(),v;
    for(int i = 0; i < sz; i++){
        v = sons[u][i];
        dp(v);

        d[u][0] += min(d[v][0], d[v][1]);
        if(d[v][2]!= maxn) d[u][1] += d[v][2];     //******************在leaves的时候可以自己代数字走走
        else d[u][1] = maxn;                       //******************这个时候d[2][1]不存在，如果其不是服务器，则其必为服务器
    }

    for(int i = 0; i < sz; i++){
        v = sons[u][i];
        d[u][2] = min(d[u][2], d[u][1] - d[v][2] + d[v][0]);
    }
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif
    // root = 0;
    while(scanf("%d", &n)){
        if(n == 0) continue;
        if(n == -1) break;

        read_tree();
        p[1] = -1;
        dfs(1,-1);                            //build the tree
        for(int i = 2; i <= n; i++){
             sons[p[i]].push_back(i);
             //cout<<i<<" "<<p[i]<<endl;       //check it before write the main program
        }
        dp(1);
        //reset
        for(int i = 1; i <= n; i++){
            sons[i].clear();
            G[i].clear();
        }
        printf("%dn", min(d[1][0], d[1][2]));       //we can use d[1][1] here.
    }
    return 0;
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx