,表示3种状态:0表示父节点放了守卫,1表示子节点放了守卫,2表示自身放了守卫
则父节点放了守卫,那么它的字节点可放可不放,我们取最小值
自身放了守卫,子节点可放可不放,去3种状态的最小值
思考子节点放了守卫的情况:
枚举哪个子节点放了守卫,即,其他子节点可放可不放,可以先用sum求出子节点值的总和,即,
表示去掉j这个子节点其他子节点的总和;
推出:;
参考代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1510;
int h[N], e[N], w[N], ne[N], idx;
int f[N][3]; // 3种状态 0 表示父节点放了守卫,1 表示子节点放了守卫,2 表示自身放了守卫
int n, m, a, b, c;
int vis[N];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int u) {
f[u][2] = w[u];
int sum = 0; // 记录所有子节点f[j][1], f[j][2] 的最小值
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]);
f[u][2] += min(f[j][0], min(f[j][1], f[j][2]));
}
f[u][1] = 1e9;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
//枚举子节点 j 放了守卫
// f[u][0] - min(f[j][1], - f[j][2]) 表示去掉j这个子节点其他子节点的总和;
f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));
}
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
memset(vis, false, sizeof vis);
for (int i = 1; i <= n; i++) {
cin >> a >> c >> m;
w[a] = c;
while (m--) {
cin >> b;
add(a, b);
vis[b] = true;
}
}
int root = 1;
while (vis[root]) root++; //寻找根节点
dfs(root);
cout << min(f[root][1], f[root][2]) << endl;
return 0;
}