您现在的位置是：首页 >技术杂谈 >P2016 战略游戏网站首页技术杂谈

题目链接：战略游戏 - 洛谷

题型：树形DP的最小点覆盖，在树中选出尽量少的节点，使得树上每一条边都至少有一端的节点被选中。

更多树形dp讲解，参见这篇链接：树形DP - dddon - 博客园

基本操作：

• 树的遍历，用DFS从根节点开始进行记忆化搜索
• 从树最深处开始往回进行DP，用子节点dp值来更新父节点dp值

这里用u表示父结点，用v表示子结点。

dp[u][0]表示不选择该父结点的最优解，则子结点必选。

dp[u][0]+=dp[v][0]

dp[u][1]表示选择该父结点的最优解，则子结点可选可不选。选那就是dp[v][1],不选就是dp[v][0],那么我们为了找到最小的人数，我们选择二者中最小的即可。

dp[u][1]+=min(dp[v][0],dp[v][1]) 

这里，题目已经说明，结点编号为从0到n-1，那么我们可以把0结点当成根结点，用dfs自底向上推导，根结点的两个最优解的最小值即为答案。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1510;
int dp[maxn][2];
 int n;
vector<int>a[maxn];
long long ans=0;

void dfs(int now,int pre)
{
    dp[now][0]=0;
    dp[now][1]=1;
    for(int i=0;i<a[now].size();i++)
    {
        int v=a[now][i];
        if(v==pre)
        {
            continue;
        }
        dfs(v,now);
        dp[now][0]+=dp[v][1];
        dp[now][1]+=min(dp[v][0],dp[v][1]);
    }

}

int main()
{
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        int v,k;
        cin>>v>>k;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            a[v].push_back(x);
            a[x].push_back(v);
        }
    }
    dfs(0,0);
    ans=min(dp[0][0],dp[0][1]);
    cout<<ans<<"
";
}