POJ 3659 Cell phone Network （树的最小点覆盖，树形DP）

题意：

给定一棵树，每个点可以覆盖自己和相邻的点，求最少要多少个点覆盖图

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 24000 + 7;
const int inf = 50000;
int N;
vector<int> G[maxn];
int deg[maxn];
int dp[maxn][3];
int root = 1;
//dp[u][0] //表示放，包括u及u的子树全部覆盖需要的最少结点数
//dp[u][1] //不放， 包括u及u子树全部覆盖需要的最少结点数
//dp[u][2] // 不放， 除了u，u的子树全被覆盖需要的最少结点数

//dp[u][0] += sum(min(dp[v][0], dp[v][1], dp[v][2]))
//放的话， 就所有状态都可以转移过来

//dp[u][1] = choose one child k use f[k][0], then sum up other children min(f[i][0], f[i][1]);
//因为u不能放， 但又要被覆盖， 说明至少有一个孩子是放的， 加上其他孩子取全部覆盖的值

//正常来说， dp[u][0]是要大于dp[u][1]的，但是如果u孩子全是叶子， 叶子是不可以被除u以外覆盖的，
//所以此时u的dp[u][1] 大于 dp[u][0]
//所以要判断是否有这种情况， 如果有的话， 那么这种情况加上dp[u][0]，其他情况（dp[v][0] > dp[v][1]）加上dp[v][1]
//否则的话挑选min(dp[v][0] * 1  + dp[v][1] * (child - 1))

//dp[u][2] += sum(dp[v][1])
//u不能被覆盖， 所以v不能放， 但v要被覆盖， 所以加上全部dp[v][1]的值



void dfs(int u, int pre) {
    dp[u][0] = 1; //放的话， 初始化为1
    dp[u][1] = G[u].size() == 1 && u != root ? inf : 0; //叶子是不能在不放的时候全覆盖的， inf， 其他赋值0
    dp[u][2] = 0;

    int minOne = inf;
    int mustPut = 0;//看一下是不是有必须放的孩子
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(v == pre)
            continue; //不访问自己父亲
        dfs(v, u);
        dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
//        dp[u][2] += min(dp[v][0], dp[v][1]);
//        if(dp[v][1] != inf)
        if(dp[v][1] >= dp[v][0]) { //满足子树如果v不放的值比放还要大,说明放才是最优的
            dp[u][1] += dp[v][0]; //直接从dp[v][0]推
            mustPut = 1;
        } else { // v不放才是最优的
            dp[u][1] += dp[v][1];//直接从dp[v][1]推
            //那么选出最少的dp[v][0] - dp[v][1], 这个点就是放的那个孩子，其他都不放

            minOne = min(minOne, dp[v][0] - dp[v][1]);
        }
        dp[u][2] += dp[v][1];
    }

    if(!mustPut) { //如果不是有必须放的， 那么挑选最少值
        dp[u][1] += minOne;
        //上面等式其实是选一个min(dp[v][0] * 1  + dp[v][1] * (child - 1))
    }
}
int main() {
//    freopen("input.txt", "r", stdin);
    while(cin >> N) {
        for(int i = 0; i < maxn; i++)
            G[i].clear();
        for(int i = 0; i < N - 1; i++) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(root, -1);
        cout << min(dp[root][0], min(dp[root][1], dp[root][2] + 1)) << "
";  //注意要把2没放那个放上去

    }
    return 0;
}

数据：

POJ 3659 Cell phone Network （树的最小点覆盖， 树形DP）

题意：

数据：

POJ 3659 Cell phone Network （树的最小点覆盖，树形DP）