1077. 皇宫看守(树状DP&选部分点看守全部点)

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#include <unordered_map>
//#include <unordered_set>
//#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define PII pair<int, int>
#define mpr make_pair
#define ms(a, b) memset((a), (b), sizeof(a))
#define x first
#define y second
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1500 + 7, M = 5000;
using namespace std;

int n;
int h[N], e[N], ne[N], w[N], idx;
int f[N][3];//第二维0这个点被父节点看到的最小花费
//第二维1这个点被子节点看到的最小花费
//第二维2这个点放警卫的最小花费
bool st[N];//找根节点
void add(int u, int v) { e[idx] = v, ne[idx] = h[u], h[u] = idx++; }
void dfs(int u) {
    f[u][2] = w[u]; //把这个点放警卫，需要的花费
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]); //被父节点看到，说明我这个点没有放警卫，那么子节点就不能找[j][0]
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);//我这个点放了，子节点就随意
    }
    f[u][1] = 1e9;
    //枚举子节点中每一个点来观察到我这个点
    //f[u][0]就是子节点的所有最小情况的和
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));
    }
}
signed main(int argc, char const* argv[]) {
    cin >> n;
    memset(h, -1, sizeof(h));
    //根据题意，可以看为有向图，从一个点开始搜
    for (int i = 1; i <= n; i++) {
        int id, cost, cnt;
        cin >> id >> cost >> cnt;
        w[id] = cost;
        while (cnt--) {
            int ver;
            cin >> ver;
            add(id, ver);
            st[ver] = true;
        }
    }
    int root = 1;
    while (st[root]) root++;
    dfs(root);
    //这个根节点没有父节点
    cout << min(f[root][1], f[root][2]) << endl;
    return 0;
}