P2899 [USACO08JAN] Cell Phone Network G——树形DP

原题

题目大意：

给一棵有\(n\)个点树，要求建造最小数量的基站，使每个点被全部覆盖
思路：

为了基站数最少，每个点必定只被覆盖一次

每个点有三种状态：

1.\(1\)表示这个点已被选择建基站
2.\(0\)表示这个点没有建基站，意味着他的父节点或子节点中有基站
3.\(-1\)表示这个点还未被选择（初始化）
贪心：基站不可以在叶子节点上

因为如果在叶子节点上基站就只可以覆盖父节点，不划算
所以用\(ret\)来记录\(x\)点的子节点的状态：

1.\(ret==1\)：\(x=0\)
2.\(ret==0\)：\(x=1\)
最后每多一个\(x==1\)，\(ans\)++

代码：

[code]#include using namespace std;const int N=1e1+10;int n,ans;vector e[N];//1：自己建基站    0：儿子建基站   int dfs(int u, int p){    int cho=-1;//choice:当前点的选择（放不放天线）     for(int y:e){          if(y!=p){            int ret=dfs(y,u);//儿子的状态             if(ret==-1)                cho=1;            else if(ret==1 && cho!=1)                cho=0;         }    }    if(cho==1) ans++;    return cho;}int main(){    cin>>n;    for(int i=1; i>a>>b;        e[a].push_back(b);        e.push_back(a);    }    if(dfs(1,0)==-1) ans++;    cout