POJ - 3659 Cell Phone Network（树形dp---树的最小点支配集）

题意：有N个点，N-1条边，任意两点可达，由此形成了一棵树。选取一个点a，它可覆盖自己以及与自己相邻的点，选取尽量少的点a，使得树中所有点都被覆盖，即求树的最小点支配集。

分析：

1、对于每一个点cur，要想使其被覆盖，有三种情况：

dp[cur][0]---在该点建立塔

dp[cur][1]---在该点的子结点建立塔

dp[cur][2]---在该点的父结点建立塔

2、对于点cur的子结点x，要使其被覆盖：

(1)dp[cur][0] += Min(Min(dp[x][0], dp[x][1]), dp[x][2]);

在cur处建塔的情况下，x可建塔，x的子节点可建塔，x的父结点即cur建塔，三者取最小值，并累加。

(2)dp[cur][2] += Min(dp[x][0], dp[x][1]);

在cur的父结点建塔的情况下，x可建塔，x的子结点可建塔，两者取最小值，并累加。

(3)dp[cur][1] += Min(dp[x][0], dp[x][1]);

在cur的子结点建塔的情况下，至少需要cur的一个子结点建塔cur才能被覆盖，所以对于每一个子结点x，x可建塔，x的子结点可建塔，两者取最小值

与此同时，记录在取最小值的情况下，cur是否有能建塔的子结点，若没有，需要将cur的一个子结点变成可建塔，选取abs(dp[x][1] - dp[x][0])最小的子结点x改变即可。

3、dp[cur][0]最后要加1，因为在cur点要建塔。

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 10000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int N;

vector<int> v[MAXN];

int dp[MAXN][5];

void dfs(int cur, int father){

    memset(dp[cur], 0, sizeof dp[cur]);

    int len = v[cur].size();

    int dif = INT_INF;

    bool ok = false;

    for(int i = 0; i < len; ++i){

        int x = v[cur][i];

        if(x == father) continue;

        if(dp[x][0] == INT_INF) dfs(x, cur);

        dp[cur][0] += Min(Min(dp[x][0], dp[x][1]), dp[x][2]);

        dp[cur][2] += Min(dp[x][0], dp[x][1]);

        dif = Min(dif, abs(dp[x][1] - dp[x][0]));

        if(dp[x][0] < dp[x][1]){

            ok = true;

            dp[cur][1] += dp[x][0];

        }

        else{

            dp[cur][1] += dp[x][1];

        }

    }

    ++dp[cur][0];

    if(!ok) dp[cur][1] += dif;

}

int main(){

    scanf("%d", &N);

    for(int i = 0; i < N - 1; ++i){

        int a, b;

        scanf("%d%d", &a, &b);

        v[a].push_back(b);

        v[b].push_back(a);

    }

    memset(dp, INT_INF, sizeof dp);

    dfs(1, -1);

    printf("%d\n", Min(dp[1][0], dp[1][1]));

    return 0;

}

巴特西

POJ - 3659 Cell Phone Network（树形dp---树的最小点支配集）

最新文章

热门文章