HDU 1054 Strategic Game (树形DP)

题面

题意：在一棵树中,每个节点能监管连接自身的一条边,问最小选取几个节点能监管树中所有的边

思路:

1.一个节点可分为两种状态-选取或不选取

2.若当前结点选取了,那么子节点可以选择不选取;若当前结点未选取,那么子节点一定要选取;

代码：

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<map> using namespace std; const int N=2000; struct E{ int val; int next; }edge[2*N+10]; int head[2*N],vis[2*N],c,dp[2*N][2]; int selMin(int x,int y) { return x<=y?x:y; } void add(int x,int y) { edge[c].val=y; edge[c].next=head[x]; head[x]=c; c+=1; } void DFS(int root) { dp[root][0]=0; //0状态表示该节点未选取 dp[root][1]=1; //1状态表示该节点被选取 vis[root]=1; for(int i=head[root];i!=-1;i=edge[i].next) { int cur=edge[i].val; if(!vis[cur]) { DFS(cur); dp[root][0]+=dp[cur][1]; dp[root][1]+=selMin(dp[cur][0],dp[cur][1]); } } } int main() { int n; while(~scanf("%d",&n)) { memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); int root; c=0; for(int i=1;i<=n;i+=1) { int p,k,x; scanf("%d:(%d)",&p,&k); if(i==1) root=p; while(k--) { scanf("%d",&x); add(p,x); add(x,p); } } DFS(root); printf("%d\n",selMin(dp[root][0],dp[root][1])); } return 0; }