HDUOJ 6268 Master of Subgraph

题目链接http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf

题意:给你一棵树,每个节点有自己的价值w_i,给定一个数字m,问1-mm个数字是否能用一个联通子图的价值和表示出来,能输出1否则输出0

思路:先不考虑联通子图这个问题,那么整个问题就是一个裸的树形背包问题,我们把树的dfs序建立出来,对于dfs序上的每一个点,考虑如果自己选那么自己子树内就可以选,否则只有在这棵子树外面才可以选。设dp[i][j]dfs序上[i,n]位置对应的节点背包容量为j是否能被表示出来,对于位置i,如果选我们就从dp[i+1]转移过来,不选我们就从dp[i+sz[id[i]]]这个位置转移过来,id[i]表示dfs序为i的节点编号是什么,sz[id[i]]表示这个节点的子树大小是多少,从后往前进行dp,最终dp[1]就是以x为根的树形背包的答案。考虑到需要联通子图,不能是一块一块的,我们即用点分治,每次求出包含重心的答案,然后递归下去即可,由于这里的m很大,所以01背包要用bitset优化,时间复杂度O(\frac{nmlogn}{64})

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair 
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=3000+10;
int T,n,m,u,v,i,root,tot,sum,f[N],w[N],sz[N],sz2[N],val[N],id[N];
bool vis[N];
vector<int>G[N];
bitset<100005>g[N],res;
void getroot(int u,int fa){
    sz[u]=1,f[u]=0;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa || vis[v]) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sum-sz[u]);
    if (f[u]<f[root]) root=u;
}
void dfs(int u,int fa){
    sz2[u]=1,val[++tot]=u,id[u]=tot;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa || vis[v]) continue;
        dfs(v,u);
        sz2[u]+=sz2[v];
    }
}
void solve(int u){
    vis[u]=1,tot=0,dfs(u,0);
    int i;
    for (i=1;i<=tot+1;i++) g[i].reset();
    g[tot+1].set(0);
    for (i=tot;i>=1;i--){
        int u=val[i];
        g[i]|=g[i+1]<<w[u];
        g[i]|=g[i+sz2[u]];
    }
    res|=g[1];
    for (i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (vis[v]) continue;
        sum=sz[v],root=0;
        getroot(v,0);
        solve(root);
    }
}
int main(){
    for (read(T);T--;){
        read(n),read(m);
        for (i=1;i<=n;i++) G[i].clear(),vis[i]=0;
        for (i=1;i<n;i++){
            read(u),read(v);
            G[u].PB(v);
            G[v].PB(u);
        }
        for (i=1;i<=n;i++) read(w[i]);
        res.reset(),sum=n,root=0,f[0]=n+1;
        getroot(1,0);
        solve(root);
        for (i=1;i<=m;i++) printf("%d",res[i]?1:0);
        puts(""); 
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注