当前位置: 代码迷 >> 综合 >> POJ1463-树形DP
  详细解决方案

POJ1463-树形DP

热度:60   发布时间:2024-01-18 01:08:45.0
//树形DP
//树的最小点覆盖
//f[x][1]以x为根的子树在x上放置的士兵的最少所需的士兵数目
//f[x][0]以x为根的子树x上不放置的士兵的最少所需的士兵数目
//状态转移方程:
//如果当前节点选取,则其子节点可选可不选dp[root][1] += min(dp[tree[root][i]][1],dp[tree[root][i]][0]) ;
//如果当前节点不选,则其子节点必须选    dp[root][0] += dp[tree[root][i]][1] ;
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
using namespace std ;
#define MAX 1510
vector<int>tree[MAX] ;
int f[MAX] , n , dp[MAX][2];void DFS(int root)
{dp[root][0]=0;dp[root][1]=1;int len = tree[root].size();for(int i = 0 ; i < len ; i ++){DFS(tree[root][i]) ;}for(int i = 0 ; i < len ; i ++){dp[root][1] += min(dp[tree[root][i]][1],dp[tree[root][i]][0]) ;dp[root][0] += dp[tree[root][i]][1] ;}
}
int main()
{int edge , fa , son ;while(scanf("%d",&n)!=EOF){