求大佬帮助 不知道错在哪里了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//树形dp
//通常使用树形结构树上dfs 用单独维度表示当前节点状态

//皇宫守卫/小胖守皇宫
//关键 使用三个0 1 2表示状态 (节点放 节点父亲放 节点子孙放)
//注意状态转移技巧 对于f[u][1]
//f[u][0]父节点监视 f[u][1]子节点监视 f[u][0]自己放置
//此时有大量重复 所以修正为
//f[u][0] 父节点监视 节点本身无 (可能存在子节点监视)
//f[u][1] 子节点监视 节点本身无 (可能存在父节点监视)
//f[u][2] 节点本身有
//以上f[u][0] f[u][1]仍然有重复 但可用计算技巧性取得min属性
//由于要求attr为min 可以重复 不影响
//通过这个重复可以快速计算出f[u][1] = min(f[u][0] - ... + ...)
const int N = 2000;
const long long inf = 0x7fffffff; 
long long f[N][3];
int h[N],e[N],ne[N];
int idx = 0;
int n;
int fa[N];
long long w[N];
void init(){
    idx = 0;
    memset(h,-1,sizeof h);
}
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u){
    f[u][1] = inf;
    f[u][0] = 0;
    f[u][2] = w[u];
    for(int j=h[u];j!=-1;j=ne[j]){
        int v = e[j];
        dfs(v);
        //自给自足
        f[u][0] += min(f[v][1],f[v][2]);
        //不需自给自足 有重叠不影响
        f[u][2] += min(min(f[v][0],f[v][1]),f[v][2]);
        //最麻烦情况 从子节点中选最小的 此时可能不止一个子节点有 
        //而且当前节点父节点可能有 而且未被选中子节点需要自给自足
        // f[u][1] = min(f[u][1],f[u][0] - min(f[v][1],f[v][2]) + f[v][2]);
        //这里写错了 必须f[u][0]最终结果得到才可以计算f[u][1]
    }
    for(int j=h[u];j!=-1;j=ne[j]){
        int v = e[j];
        f[u][1] = min(f[u][1],f[u][0]-min(f[v][1],f[v][2])+f[v][2]);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int l,k,r;
    init();
    for(int i=0;i<n;i++){
        cin>>l>>w[l]>>k;
        for(int i=0;i<k;i++){
            cin>>r;
            add(l,r);
            fa[r] = l;
        }
    }
    int root = 1;
    while(fa[root]) root++;
    dfs(root);
    //树根节点不可能有f[u][0]
    cout<<min(f[root][1],f[root][2])<<endl; 
    return 0;
}

第一个测试点通过,其余测试点wa
loj上可以A掉

0 条评论

目前还没有评论...

信息

ID
1144
难度
7
分类
动态规划 | 树形DP 点击显示
标签
递交数
4600
已通过
1007
通过率
22%
被复制
10
上传者