精华内容
下载资源
问答
  • 树形依赖背包

    千次阅读 2017-08-03 20:18:29
    树形依赖背包

    问题大意:给出一棵树,根节点为1,每个点有毒素和收获。要求毒素不超过给定值的情况下使收获最大。一个点的父亲节点被选取后这个点才能被选取。

    首先弄出dfs序,也记录下每个点其子树及自身的大小。每个点都能够被选或不选,如果选了才会考虑它子树。
    f[i][j]表示dfs序上第i位上的点在其子树及自身上选取了毒素和为j的点所能获得的最大收益。(下面x指dfs序上第i位代表的点)

    如果j<cost[x]f[i][j]=f[i+size[x]][j]。代表这个点及其子树都不能选(+size[x]代表在dfs序上跳过这个点的子树)
    如果jcost[x]f[i][j]=max(f[i+1][jc[x]]+v[x],f[i+size[x]][j])
    注意是否会出现负收益,并选择是否需要再与0比较。

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    using namespace std ;
    bool Read ( int &x, char c = getchar(), bool flag = false ) {
        for ( x = 0 ; !isdigit(c) ; c = getchar() ) if ( c == EOF ) return false ; else if ( c == '-' ) flag = true ;
        for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ; if ( flag ) x = -x ;
        return true ;
    }
    const int maxn = 5010, maxm = maxn<<1, zhf = 1<<28 ;
    int ans, n, m, e, be[maxn], to[maxm], nxt[maxm], v[maxn], c[maxn], dfn[maxn], rdn[maxn], clk, size[maxn], f[maxn][maxn] ;
    void add ( int x, int y ) {
        to[++e] = y ;
        nxt[e] = be[x] ;
        be[x] = e ;
    }
    void dfs ( int x, int fa ) {
        ( dfn[x] = ++clk )[rdn] = x ;
        size[x] = 1 ;
        int i, u ;
        for ( i = be[x] ; i ; i = nxt[i] ) {
            u = to[i] ;
            if ( u == fa ) continue ;
            dfs(u,x) ;
            size[x] += size[u] ;
        }
    }
    int main() {
        int i, j, k, x, y, z ;
        Read(n) ; Read(m) ;
        for ( i = 1 ; i <= n ; i ++ ) {
            Read(v[i]) ;
            Read(c[i]) ;
        }
        for ( i = 1 ; i < n ; i ++ ) {
            Read(x) ; Read(y) ;
            add ( x, y ) ;
            add ( y, x ) ;
        }
        dfs(1,1) ;
        for ( i = n ; i ; i -- ) {
            x = rdn[i] ;
            for ( j = 0 ; j <= m ; j ++ )
                if ( j < c[x] ) f[i][j] = max ( f[i+size[x]][j], 0 ) ;
                else f[i][j] = max ( max( f[i+1][j-c[x]]+v[x], f[i+size[x]][j] ), 0 ) ;
        }
        printf ( "%d\n", f[1][m] ) ;
        return 0 ;
    }

    感谢Wearry在模拟赛中提到这个知识点。

    展开全文
  • 树形dp+树形依赖背包

    2018-10-15 19:28:00
    最近集训队大佬开了树形依赖背包的讲座,感觉还是学到了东西,就是对树形dp的理解方式更多了一种 首先接触到了两种树形dp的写法:第一种是直接在树上进行dp,另一种是在dfs序上进行dp,我较偏于后者,后者想法可以很清晰,...

    最近集训队大佬开了树形依赖背包的讲座,感觉还是学到了东西,就是对树形dp的理解方式更多了一种

    首先接触到了两种树形dp的写法:第一种是直接在树上进行dp,另一种是在dfs序上进行dp,我较偏于后者,后者想法可以很清晰,

    当然大佬们请自动略过

    1.hdu1561(树形依赖背包裸题)

    解法1:dp[i][j]代表选取范围为 dfs序大于等于i的所有点 所能得到的最大值(这个定义..非常不准确,正着来的话..我还没想清楚细节)

    能转移到dp[i][j]的点只有两种情况,运用01背包的思想,选择这个点,或者不选择这个点,

    即dp[i][j]=max(dp[i+1][j-w[x]]+v[x],dp[i+size[x]][j]);

    #include<bits/stdc++.h>
    using namespace std;
    const int N=300;
    vector<int>g[N];
    int now,pos[N],r[N],size[N];
    void dfs(int u){
        pos[++now]=u;size[u]=1;
        for(auto v:g[u]) dfs(v),size[u]+=size[v];
        r[u]=now;
    }
    int dp[N][N],v[N];
    int main(){
        int n,m,a,b;
        while(~scanf("%d%d",&n,&m)){
            if(n==0&&m==0) break;now=0;
            for(int i=1;i<=n+1;i++) for(int j=1;j<=n+1;j++) dp[i][j]=0;
            for(int i=0;i<=n;i++) g[i].clear();
            for(int i=1;i<=n;i++){
                scanf("%d%d",&a,&v[i]);
                g[a].push_back(i);
            }
            dfs(0);m++;
            for(int i=n+1;i;i--){
                int x=pos[i];
                for(int j=1;j<=m;j++)
                    dp[i][j]=max(dp[i+1][j-1]+v[x],dp[i+size[x]][j]);
            }
            printf("%d\n",dp[1][m]);
        }
        return 0;
    }
    View Code

     解法2:运用树形dp独特的优化,枚举有效的元素

    dp[i][j]代表在以i为根的子树中选择j个元素所能容纳的最大值

    #include<bits/stdc++.h>
    using namespace std;
    const int N=300;
    vector<int>g[N];
    int now,pos[N],l[N],siz[N];
    int dp[N][N],v[N],n,m,a;
    void dfs(int u){
        siz[u]=1;dp[u][1]=v[u];
        for(auto v:g[u]){
            dfs(v);
            for(int i=siz[u];i>=1;i--)
            for(int j=0;j<=siz[v]&&i+j<=m;j++){
                dp[u][i+j]=max(dp[u][i+j],dp[u][i]+dp[v][j]);
            }
            siz[u]+=siz[v];
        }
        //枚举有效的元素 
    }
    int main(){
        while(~scanf("%d%d",&n,&m)){
            if(n==0&&m==0) break;now=0;
            memset(dp,0,sizeof(dp));
            memset(siz,0,sizeof(siz));
            for(int i=0;i<=n;i++) g[i].clear();
            for(int i=1;i<=n;i++){
                scanf("%d%d",&a,&v[i]);
                g[a].push_back(i);
            }
            m++;dfs(0);
            printf("%d\n",dp[0][m]);
        }
        return 0;
    }
    View Code

    解法3:讲解的全局动归和正着来的dfs序.......觉得他们给的代码是错的,反正我当模板代进去,样例都过不了....

    2.codeforces 815C

    解法:运用树形dp的独特优化,达到n^2的复杂度,想一下这些串的链接方式,在考虑儿子和父亲合并的时候,可能

    1.父亲不用券,儿子也不用券,

    2.父亲用券,儿子不用券

    3.父亲用,儿子也用,

    只有这三种情况

    所以用二维的枚举有效元素,即可解决,注意遍历的顺序

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=5e3+10;
    vector<int>g[N];int n,b,x,now;
    int c[N],d[N],pos[N],siz[N];
    int dp1[N][N],dp2[N][N];
    //dp1用券,dp2不用券 
    void dfs(int u){
        dp2[u][0]=0;siz[u]=1;
        dp1[u][1]=c[u]-d[u];dp2[u][1]=c[u];
        for(int z=0;z<g[u].size();z++){
            int v=g[u][z];dfs(v);
            for(int i=siz[u];i>=0;i--)
            for(int j=0;j<=siz[v];j++){
                dp1[u][i+j]=min({dp1[u][i+j],dp1[u][i]+dp1[v][j],dp1[u][i]+dp2[v][j]});
                dp2[u][i+j]=min(dp2[u][i+j],dp2[u][i]+dp2[v][j]);
            }
            siz[u]+=siz[v];
        } 
    }
    int main(){
        memset(dp1,0x3f,sizeof(dp1));
        memset(dp2,0x3f,sizeof(dp2));
        scanf("%d%d",&n,&b);scanf("%d%d",&c[1],&d[1]);
        for(int i=2;i<=n;i++){
            scanf("%d%d%d",&c[i],&d[i],&x);
            g[x].push_back(i);
        }
        dfs(1);
        for(int i=n;i>=1;i--){
            if(dp1[1][i]<=b||dp2[1][i]<=b) {
                printf("%d\n",i);return 0;
            }
        }
        printf("0\n");
        return 0;
    }
    View Code

     3.(NAIPC2018)I - Red Black Tree

    题意:一棵树,n个点,m个红点,问选择k个点的子集数(且保证子集里的元素不互为祖先)

    解法:

      (1)树形dp

      运用枚举子树的有效元素,f[i][j]代表以i为根的子树中选取j个红点的方案数,考虑该点取还是不取即可解决

    #include<bits/stdc++.h>
    using namespace std;
    const int mod=1e9+7;
    const int N=2e5+10;
    vector<int>g[N];int clr[N];
    int dp[N][1100],siz[N],n,m,x,h[N];
    void dfs(int u){
        siz[u]=clr[u];dp[u][0]=1;
        for(auto v:g[u]){
            dfs(v);
            for(int i=0;i<=siz[u]+siz[v];i++) h[i]=0;
            for(int i=0;i<=siz[u]&&i<=m;i++)
            for(int j=0;j<=siz[v]&&i+j<=m;j++){
                h[i+j]=(1ll*dp[u][i]*dp[v][j]+h[i+j])%mod;
            }
            for(int i=0;i<=siz[u]+siz[v];i++) dp[u][i]=h[i];
            siz[u]+=siz[v];
        }
        dp[u][clr[u]]++;
    } 
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=2;i<=n;i++){
            scanf("%d",&x);
            g[x].push_back(i);
        }
        for(int i=1;i<=m;i++) scanf("%d",&x),clr[x]=1;
        dfs(1);
        for(int i=0;i<=m;i++) printf("%d\n",dp[1][i]);
        return 0;
    }
    View Code

      (2)dfs序解决(跟上面的正着的dfs序问题,,,还没理清)

    启发:(计算符合条件的集合数量)这对于这种求子集个数的问题,形象的展示了,考虑一个点在集合中和不在集合中这种解法,既像是01背包,又像是二进制算法...但都有一个特别的性质,即这样做能将所有的状态给考虑全>>>>

    转载于:https://www.cnblogs.com/vainglory/p/9794091.html

    展开全文
  • HDU - 1561树形依赖背包

    2019-08-27 21:54:44
    HDU - 1561树形依赖背包 题目: 传送门 思路见代码注释. 代码: /* 对于每个节点u,要么有唯一的父亲fa,要么没有父亲,自形一颗树 所以按照题目给的要求该图是一个森林. 我们考虑将森林中的每一颗树的根连接到超级根...

    HDU - 1561树形依赖背包

    题目: 传送门

    思路见代码注释.
    代码:

    /*
    对于每个节点u,要么有唯一的父亲fa,要么没有父亲,自形一颗树
    所以按照题目给的要求该图是一个森林.
    我们考虑将森林中的每一颗树的根连接到超级根root.那么形成的图是一个以超级根
    为根的树,题目也转化为从该树上取m+1个节点,使得价值最大,取u节点必须先取父亲节点.
    这就是树形依赖背包的问题了
    */
    #include<bits/stdc++.h>
    #define mset(a,b) memset(a,b,sizeof(a))
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> P;
    const int inf=0x3f3f3f3f;
    const int N=1e4+10;
    const int mod=1e9+7;
    int w[305];
    vector<int> g[305];
    int dp[305][305];
    int n,m;
    void dfs(int u)
    {
        for(int v:g[u])
        {
            dfs(v);
            /*因为要求该儿子中要么只取一个,要么不取, 所以我们必须先枚举背包容量从大到小,其次枚举儿子的容量大小*/
            for(int s=m;s>=1;--s)//枚举背包容量从大到小
            {
                for(int a=1;a<=s;++a){//其次枚举儿子容量
                    dp[u][s]=max(dp[u][s],dp[u][s-a]+dp[v][a]);
                }
            }
        }
        dp[u][0]=0;
        for(int i=m;i>=1;--i)
            dp[u][i]=dp[u][i-1]+w[u];
    
    }
    int solve()
    {
        dfs(0);
        return dp[0][m];
    }
    int main()
    {
        ios::sync_with_stdio(false);cin.tie(0);
        while(cin>>n>>m,n)
        {
            for(int i=0;i<=n;++i) g[i].clear();
            for(int i=1;i<=n;++i){
                int fa,ww;
                cin>>fa>>ww;
                w[i]=ww;
                g[fa].push_back(i);
            }
            ++m;//0这个节点额外的且是必须取的,所以m要+1
            mset(dp,0);
            cout<<solve()<<endl;
        }
        return 0;
    }
    
    展开全文
  • 树形依赖背包

    http://codevs.cn/problem/1155/


    dfs自然的生成依赖关系

    然后搜索前update

    搜索后dp转移一下

    为了方便,令root=0

    将森林构建成树

    具体看代码


    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <vector>
    #include <cmath>
    #include <queue>
    #include <map>
    #include <set>
    using namespace std;
    inline void read(int &ans){
      ans=0;char x=getchar();int f=1;
      while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
      while(x>='0'&&x<='9')ans=ans*10+x-'0',x=getchar();
      ans*=f;
    }
    const int MAXN=60+10;
    const int MAXM=30000+10;
    struct node{int v,next;}E[MAXN<<1];
    int head[MAXN<<1],tot,val[MAXN],cost[MAXN],n,m,ans,F[MAXN][MAXM];
    void add(int u,int v){E[++tot]=(node){v,head[u]},head[u]=tot;}
    
    void dfs(int u,int fa,int M){
      if(M>0)
        for(int i=head[u];~i;i=E[i].next){
          int v=E[i].v;
          if(v!=fa){
    	for(int j=0;j<=m-cost[v];++j)
    	  F[v][j]=F[u][j]+cost[v]*val[v];
    	dfs(v,u,m-cost[v]);
    	for(int j=cost[v];j<=m;++j)
    	  F[u][j]=max(F[u][j],F[v][j-cost[v]]);
          }
        }
    }
    
    int v;
    int main(){
      read(m),read(n);
      memset(head,-1,sizeof(head));
      for(int i=1;i<=n;i++)
        read(cost[i]),read(val[i]),read(v),add(i,v),add(v,i);
      dfs(0,0,m);
      printf("%d\n",F[0][m]);
      return 0;
    }


    展开全文
  • 树形依赖背包问题 每个点有个权值和体积,如果选了某个点那么它的父亲也必须选,问体积和<=m的最大权值和。 如果体积都为1,那么直接做是$n^2$的。 否则是$nm^2$的。 我们考虑求出树的后序遍历,那么对于$i$...
  • 树形依赖背包是子树依赖父亲才能产生贡献的一类问题。 有两种解决的办法: 1.强制选择当前节点,用当前的状态去更新子树信息,然后再用子树信息更新父亲。 2.对于这一类问题,只有选择了父亲节点,才能选择子树。...
  • 树形依赖背包指的就是一类具有树形依赖关系的背包问题。当选一个物品的前提是选另一件物品,而这些依赖关系构成了一个树形关系。在容量有限的情况下,然后求最大的价值,这类问题我们就称之为树形依赖背包树形...
  • 树形依赖背包板子题 树形依赖背包大概就是说:对于一个点,只有选了它的父亲才能选自身 把dfs序建出来,倒过来考虑 设\(f[i][j]\)表示从第\(i\)个节点往后背包体积为\(j\)的最大价值 转移的时候,只有选了该点才能从...
  • 题意 有一辆能载客m的车,有n个人,然后第i个人上车的条件是第a[i]个人要上车,问最多能上几个。 (题意很简单吧。...首先要明确一点,这些人的...子树是依赖于根节点的,这就变成了典型的树形依赖背包了,另外想着
  • 【LuoguP1273有线电视网】树形依赖背包 参考论文http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html 参考一篇写的很好的博文...
  • 菜菜推荐的“水题”虐了我一天T T...(菜菜好强强qwq~  显然是个分数规划题,二分答案算出p[i]-mid*s[i]之后在树上跑依赖背包,选k... 树形依赖背包的普遍做法是按dfs序DP,设f[i][j]为dfs序为i的点,已经选了j个...
  • CTSC 97 选课 ----树形依赖背包

    千次阅读 2013-11-20 20:36:13
    树形依赖背包问题:给定n件物品和一个背包。第 i 件物品的价值是 wi ,其体积为 Vi ,但是依赖于第 Xi 件物品(必须选取 Xi 后能取 i ,如果无依赖则 Xi = 0),依赖关系形成森林,背包的容量为 C 。可以任意选择装入...
  • BZOJ 洛谷 \(shadowice\)已经把他的思路说的很清楚了,可以先看一下会更好理解? 这篇主要是对\(Claris\)题解的简单说明。与\(shadowice\)的做法...问题等价于树形依赖背包,允许一条链每个点各免费取一次。 免费...
  • 树形依赖背包模板

    2018-04-28 21:36:07
    这种背包并不是简单的选取最优,有些会遇到一些限制条件,比如选a必须先选b,那怎么办,这里需要用到dfs序,dfs序是个很神奇的东西,大家都知道深搜的过程,在回溯时,它一定是由儿子节点回溯到父亲节点,这样的话,...
  • 树形依赖背包动态规划 还是先看一下题: Description现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值...
  • BZOJ 题目的限制即:给定一棵树,只能任选一个连通块然后做背包,且每个...如果物品数量为\(1\),那就是一个树形依赖背包(选儿子必须选父亲),用DFS序优化转移:\(f[i][j]=\max(f[i+1][j-v_i]+w_i,\ f[i+sz_i][j]...
  • 题意 给出一棵树,每个节点有一个权值。...只要枚举每个点,然后以这个点为根做一次树形依赖背包就好了。 做完之后发现并不能跑过去。 考虑优化,当不小于点x的节点数小于k时,就可以直接退出...
  • 今天才发现自己根本不会树形背包,我太菜了。  一般的树形背包是这样做的:  看上去,它的复杂度是 $O(nk^2)$ 的。 第一种优化:  这里,如果第二维的大小和子树大小有关,同时又不超过一个常数 $k$ 。...
  • 注意是一个无根,需要构造虚拟结点0结点,o结点直接赋值0就行。 代码注释很详细,下面还有一直做法,但推荐第一种做法,第二种做法在一些题目不适用 第一种代码实现: #include #include #include #...
  • 题目大意: ...这种类型的树形dp就比较明显了 考虑dp[u][k]代表从u节点出发选了k个物品的最大值,因为存在依赖关系; 所以注意状态转移时,特别注意dp[u][0]这个不合法状态不要计入到转移内 由

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 373
精华内容 149
热门标签
关键字:

树形依赖背包