斯德哥尔摩 的博客

斯德哥尔摩 的博客

P1273 有线电视网

posted on 2018-10-24 20:31:07 | under 刷题 |

P1273 有线电视网

这是一个树上背包。

设$dp[i][j]$表示在$i$节点,选$j$个用户,能得到的钱的最大值,然后对每个节点做分组背包。

什么?你不知道分组背包???

分组背包:若干组物品,每组中的物品互相冲突,即:每组中最多只能选一件物品,求最大价值。

怎么看出是分组背包?

首先,背包的总容量相当于该点为根节点的子树中所有的用户数量,即:$dp[i][j]$的$j$不可能超过它连接的所有用户数。

然后,把该节点的每个子树看成一组,每组中的元素为选$1,2,3,...,k$个用户。

于是转移方程破壳而出:$$dp[i][j]=\max\{dp[i][j-k]+dp[v][k]-cost[i][j]\quad|\quad\text{v为i的儿子}\}$$

$k$表示枚举到这组中的元素,即:选$k$个用户。

$cost[i][j]$为$i,j$之间的边的耗费。

最后输出$dp[1][i]>=0$的i的最大值,反向枚举就好。

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 3010
using namespace std;
int n,m,c=1;
int val[MAXN],head[MAXN],dp[MAXN][MAXN];
struct Edge{
    int next,to,w;
}a[MAXN*MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline void add_edge(int u,int v,int w){
    a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
}
int dfs(int rt){
    dp[rt][0]=0;
    if(rt>n-m){
        dp[rt][1]=val[rt];
        return 1;
    }
    int sum=0,s;
    for(int i=head[rt];i;i=a[i].next){
        int will=a[i].to;
        s=dfs(will);
        sum+=s;
        for(int j=sum;j>0;j--)
        for(int k=1;k<=s;k++)
        if(j-k>=0)
        dp[rt][j]=max(dp[rt][j],dp[rt][j-k]+dp[will][k]-a[i].w);
    }
    return sum;
}
void work(){
    for(int i=m;i>=1;i--)
    if(dp[1][i]>=0){
        printf("%d\n",i);
        break;
    }
}
void init(){
    int x,y,k;
    n=read();m=read();
    memset(dp,-127,sizeof(dp));
    for(int i=1;i<=n-m;i++){
        k=read();
        while(k--){
            x=read();y=read();
            add_edge(i,x,y);
        }
    }
    for(int i=n-m+1;i<=n;i++)val[i]=read();
    dfs(1);
}
int main(){
    init();
    work();
    return 0;
}