战略游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 861 字

在树的节点上放置最少的士兵，使每条边都被至少

一本通
例

正文

/*
原题：战略游戏（一本通 5.2 例4）
题意：在树的节点上放置最少的士兵，使每条边都被至少一个端点上的士兵瞭望到（最小点覆盖）。
思路：树形 DP。dp[u][0] 表示 u 不放士兵，则儿子必须放；dp[u][1] 表示 u 放，儿子可放可不放。取根处最小值。
复杂度：O(N) 时间，O(N) 空间。
易错点：u 不放时所有相邻边必须由儿子覆盖；无向边建图后任取根（如 0）。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1505;
vector<int> g[N];
int dp[N][2];
void dfs(int u,int fa){
    dp[u][0]=0;
    dp[u][1]=1;
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u][0]+=dp[v][1];
        dp[u][1]+=min(dp[v][0],dp[v][1]);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int id,k;
        cin>>id>>k;
        for(int j=0;j<k;j++){
            int r;
            cin>>r;
            g[id].push_back(r);
            g[r].push_back(id);
        }
    }
    dfs(0,-1);
    cout<<min(dp[0][0],dp[0][1])<<"\n";
    return 0;
}

战略游戏

正文

一本通·提高篇的其它内容