洛谷P2016 战略游戏 题解

题目链接：P2016 战略游戏

题意： Bob 要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。

注意这里是相邻的边，不是相邻的结点

显然我们需要记录与子结点所连的边是否被监视

于是有

$$dp[u][0]=\sum dp[v][1]\\ dp[u][1]=\sum \min(dp[v][0],dp[v][1])$$

然后就没了

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)

int n,dp[N][2];
vector<int> vec[N];
void addEdge(int u,int v)
{
    vec[u].push_back(v);
    vec[v].push_back(u);
}
void dfs(int u,int f)
{
    dp[u][1]=1;dp[u][0]=0;
    for(int v : vec[u])
    {
        if(v==f)continue;
        dfs(v,u);
        dp[u][0]+=dp[v][1];
        dp[u][1]+=min(dp[v][1],dp[v][0]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v,m; i<=n; i++)
    {
        cin >> u >> m;
        for(int j=1; j<=m; j++)
            cin >> v,addEdge(u+1,v+1);
    }
    dfs(1,1);
    cout << min(dp[1][0],dp[1][1]) << endl;
    return 0;
}