C++ 代码

0被父节点看到 1被子节点看到 2自己有

1、f[u][0] 如果点i被父节点看到，它的子节点j可以放守卫也可以不放，所以累加min(f[j][1],f[j][2])
2、f[u][2] 如果点i自己有，它的子节点j可以选择被父节点看到也可以选择自己放也可以选择被子节点看到，所以累加min{f[j][0],f[j][1],f[j][2]}
3、f[u][1] 如果点i被子节点看到，那么要枚举被哪个子节点看到，记被子节点j看到;
           那么子节点j肯定要选择放守卫f[j][2];
           对于其他的子节点可以选择放守卫或不放守卫，等价于除去节点j的第一种情况,
           即f[i][0]-min(f[j][1] , f[j][2]).
           所以要求f[u][1]的最小值，就要枚举所有i的子节点，
           不断对f[i][1]取min(f[i][1] , f[j][2] + f[u][0]-min(f[j][1] , f[j][2])

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1510;

int e[N] , ne[N] , w[N] , h[N] , idx;
int f[N][3];
int n;
bool st[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];

    for(int i = h[u] ; ~i ; 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][2] , f[j][1]));
    }

    f[u][1] = 1e9;
    for(int i = h[u] ; ~i ; 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]));
    }
}

int main()
{
    cin >> n;

    memset(h , -1 , sizeof h);
    for(int i = 0 ; 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;
}