Perfect Service

题意：

n个节点树，在一个节点放上一台服务器可以给相邻的其他各点提供服务且一个节点只能接受一台服务器，求使n个节点都被服务放的服务器的最小数量。

分析：

不算太难，状态想的差不多，但是考虑不全面状态方程写错了，要多练啊！！！状态好想，一个节点服务器放法有3中，放在自身，放在父节点，放在孩子节点

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define N 10010

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

int used[],dp[N][],n;

vector<int>e[N];

void dfs(int root){

    used[root]=;

    for(int i=;i<e[root].size();++i){

        int son=e[root][i];

        if(used[son])continue;

        dfs(son);

        dp[root][]+=min(dp[son][],dp[son][]);//自己为服务器

        dp[root][]+=dp[son][];//以父节点为服务器

        dp[root][]=min(dp[root][],dp[son][]-dp[son][]);

    }

    dp[root][]+=dp[root][];//以子节点为服务器

}

int main()

{

    while(~scanf("%d",&n)){

        if(n==-)break;

        if(n==)continue;

        for(int i=;i<=n;++i){

            e[i].clear();

            dp[i][]=;

            dp[i][]=;

            dp[i][]=INF;

        }

        int u,v;

        for(int i=;i<n-;++i)

        {

            scanf("%d%d",&u,&v);

            e[u].push_back(v);

            e[v].push_back(u);

        }

        memset(used,,sizeof(used));

        dfs();

        printf("%d\n",min(dp[][],dp[][]));

    }

return ;

}

dp[root][0]+=min(dp[son][0],dp[son][1]);//自己为服务器

        dp[root][1]+=dp[son][2];//以父节点为服务器

        dp[root][2]=min(dp[root][2],dp[son][0]-dp[son][2]);

相关文章