树形DP 90pts求调
查看原帖
树形DP 90pts求调
559920
nrs1234楼主2024/11/26 18:49

这里第五个测试点一直过不了

#include<bits/stdc++.h>
using namespace std;
const int N=1510,INF=1e6;
int n,f[N][3],w[N],id,ns,son;
vector<int> v[N];
void slove(int u,int fa){
    bool flag=false;
    for(int i:v[u]){
        if(i==fa) continue;
        if(f[i][2]<=f[i][1]){
            f[u][1]+=f[i][2];
            flag=true;
        }
        else f[u][1]+=f[i][1];
    }
    if(!flag){
        int add=0x3f3f3f3f;
        for(int i:v[u]){
            if(i==fa) continue;
            add=min(add,f[i][2]-f[i][1]);
        }
        f[u][1]+=add;
    }
    return;
}
void dfs(int u,int fa){
    f[u][2]=w[u];
    if(v[u].size()==1){
        f[u][0]=0;
        f[u][1]=INF;
        return;
    }
    for(int i:v[u]){
        if(i==fa) continue;
        dfs(i,u);
        f[u][2]+=min(f[i][0],min(f[i][1],f[i][2]));
        f[u][0]+=f[i][1];
    }
    slove(u,fa);
    return;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&id);
        scanf("%d%d",&w[id],&ns);
        for(int j=1;j<=ns;j++){
            scanf("%d",&son);
            v[id].push_back(son);
            v[son].push_back(id);
        }
    }
    dfs(1,-1);
    printf("%d",min(f[1][1],f[1][2]));
    return 0;
}
2024/11/26 18:49
加载中...