[LuoguP1273] 有线电视网

题解

树上背包。定义 表示在 中选 个用户的最大利润(可能为负)。目标即满足 的最大的 .

对于结点 ,将其子结点作为分组,做分组 01 背包。令 表示遍历前 个子结点,选 个用户的最大利润。则对于当前子结点 ,使用

对每个 更新(其中 要倒序循环, 表示 中的用户的个数, 表示 到父结点 的传输费用)

注意初始化的时候, .

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=3003;
int n,m;
int p[N],s[N],v[N],b[N],mon[N],f[N][N];
void add_son(int par,int son,int val){p[son]=par,b[son]=s[par],s[par]=son,v[son]=val;
}
int dfs(int u){if(u>n-m)return 1;
    int sz=0,t;// 目前的用户总数;当前子树的用户数
    for(int i=s[u];i;i=b[i]){t=dfs(i),sz+=t,f[i][0]=0;
        for(int j=sz;j>0;j--){//01 背包
            for(int k=1;k<=t;k++){if(k>j)break;// 在当前子树选 k 个用户
                f[u][j]=max(f[u][j],f[u][j-k]+f[i][k]-v[i]);
            }
        }
    }
    return sz;
}
int main(){scanf("%d%d",&n,&m);
    //initialize
    memset(f,~0x3f,sizeof(f));
    FOR(i,1,n)f[i][0]=0;
    //read
    FOR(i,1,n-m){int k,ai,ci;scanf("%d",&k);
        FOR(j,1,k){scanf("%d%d",&ai,&ci);
            add_son(i,ai,ci);
        }
    }
    FOR(i,1,m)scanf("%d",&f[n-m+i][1]);
    dfs(1);
    for(int i=n;i>=0;i--){if(f[1][i]>=0){printf("%d",i);return 0;}
    }
    return 0;
}

 上一篇
[HDU2196]Computer [HDU2196]Computer
二次扫描与换根法这种算法通常用于统计无根树上每个结点的答案,并且对于根结点的答案容易统计的题目。这时,我们就把每个结点在 DFS 遍历的同时换作根,同时统计答案。 我们对整棵树做 2 次 dfs: 第一次: 选定一个结点为根(比如 1 号)
2018.11.08
下一篇 
[LuoguP1637] 三元上升子序列 [LuoguP1637] 三元上升子序列
题解对于 ,考虑在它前面比它小的数的个数记为 ,在它后面比它打的数的个数记为 ,相乘累加到答案。 显然,离散化一下后可以用树状数组统计。 具体方法是离散化后,遍历数组时把当前元素的值当作下标,在该下标的位置上
2018.11.08
  目录