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\)++
代码：
#include using namespace std;const int N=1e1+10;int n,ans;vector e;//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.push_back(b); e.push_back(a); } if(dfs(1,0)==-1) ans++; cout
页:
[1]