皇宫看守

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

树上每点可放看守，需看守所有点，求最小总费用

一本通
例

正文

/*
原题：皇宫看守（一本通 5.2 例5）
题意：树上每点可放看守（有费用），需看守所有点，求最小总费用（最小支配集）。
思路：三态 DP。dp[u][0] 放；dp[u][1] 不放但被父覆盖（儿子必须放）；dp[u][2] 不放被某儿子覆盖（儿子中至少一个放）。取根的最小值。
复杂度：O(N) 时间，O(N) 空间。
易错点：dp[u][1] 时所有儿子必须放（边 u-v 只能由 v 守）；dp[u][2] 需保证至少一个儿子放，否则要补最小代价。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1505;
const int INF=1e9;
vector<int> g[N];
int cost[N];
int dp[N][3];
void dfs(int u,int fa){
    dp[u][0]=cost[u];
    dp[u][1]=0;
    int base=0;
    bool haschild=false;
    int mindelta=INF;
    for(int v:g[u]){
        if(v==fa)continue;
        haschild=true;
        dfs(v,u);
        dp[u][0]+=min({dp[v][0],dp[v][1],dp[v][2]});
        dp[u][1]+=dp[v][0];
        int mn=min(dp[v][0],dp[v][2]);
        base+=mn;
        mindelta=min(mindelta,dp[v][0]-mn);
    }
    if(!haschild)
        dp[u][2]=INF;
    else
        dp[u][2]=base+(mindelta>0?mindelta:0);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int id,k;
        cin>>id>>cost[id]>>k;
        for(int j=0;j<k;j++){
            int r;
            cin>>r;
            g[id].push_back(r);
            g[r].push_back(id);
        }
    }
    dfs(1,-1);
    cout<<min({dp[1][0],dp[1][1],dp[1][2]})<<"\n";
    return 0;
}

皇宫看守

正文

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