第十七次CCF计算机软件能力认证 第五题 城市规划（分组背包、树形dp）

转载：来源

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;
#define int long long
const int N=5e4 10;
int n,m,K,e[N<<1],ne[N<<1],h[N],idx,w[N<<1];
int f[N][110],ans=LLONG_MAX,sz[N],st[N];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx  ;
}
void dfs(int u,int fa){
    f[u][0]=0;
    if(st[u])f[u][1]=0;
    sz[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs(j,u);
        sz[u] =sz[j];
        for(int j=K;j>=0;j--){
            for(int k=0;k<=j;k  ){
                f[u][j]=min(f[u][j],f[u][j-k] w[i]*(K-k)*k f[e[i]][k]);
            }
        }
    }
    ans=min(ans,f[u][K]);
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&K);
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i  ){
        int x;
        scanf("%lld",&x);
        st[x]=1;
    }
    for(int i=0;i<n-1;i  ){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    memset(f,0x3f,sizeof f);
    dfs(1,-1);
    cout<<ans<<endl;
}

dp

0 人点赞