题解 P1273 【有线电视网】

· · 题解

在我之前写的18篇题解里，没有一个我能看懂的。

（我太弱了）

另外，我真的不熟链式前向星（好像其他题解都是），

我用邻接表的。（就是2维数组）

正文

思路不难的，f[i][j]表示对于第i个点，让j个用户看上比赛最多赚多少钱。

需要注意一下的是f[i][j]开始时要负无穷大，f[i][0]要等于0。

然后就dp算出f[i][j],最后找到最大的j使得f[i][j]>=0，输出。

那么，怎么dp呢？抄题解呗

这里用到的就是分组背包了。

//分组背包：有若干组物品，每组最多拿一个物品
//而这里，每个节点是一个背包，子节点的个数是组数，
//每组的选择互相冲突（要么不给观众看，要么给1个，要么给2个，…）
//所以这里的条件和分组背包是一样的
for(int i=1;i<=组的总数;i++)
      for(int j=最大背包容量;j>=1;j--)
        for(int k=1;k<=组里物品总数;k++)
        {
            进行dp
        }

那么可以写程序了。

代码

#include<cstdio>
#include<cstring>
int max(int p,int q){return p>=q?p:q;}
int n,m;
int mo[3001][3001];//节点i到它第j个子节点要多少钱
int K[3001]；//节点i有几个子节点
int S[3001]={0};//以节点i为根节点的子树里有几个用户
int f[3001][3001];
int ch[3001][3001];//节点i的第j个子节点的编号
bool b[3001]={0};//f[i][]是否计算过
void dfs(int x)
{
    b[x]=1;
    for(int i=1;i<=K[x];i++)//每一组（每个子结点） 
      for(int j=S[x];j>=1;j--)//背包容量（多少观众） 
        for(int k=1;k<=S[ch[x][i]] && k<=j;k++)//遍历
        {
            if(b[ch[x][i]]==0) dfs(ch[x][i]);
            f[x][j]=max(f[x][j],f[x][j-k]+f[ch[x][i]][k]-mo[x][i]);
        }
}
int SS(int x)
{
    if(S[x]) return S[x];
    if(x>=n-m+1) return S[x]=1;
    for(int i=1;i<=K[x];i++)
        S[x]+=SS(ch[x][i]);
    return S[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(f,-0x3f,sizeof(f));
    for(int i=1;i<=n-m;i++)
    {
        scanf("%d",&K[i]);
        for(int j=1;j<=K[i];j++)
            scanf("%d%d",&ch[i][j],&mo[i][j]);
    }
    for(int i=n-m+1;i<=n;i++) scanf("%d",&f[i][1]),b[i]=1;
    for(int i=1;i<=n;i++) f[i][0]=0;
    SS(1);//计算S[i]
    dfs(1);//计算f
    for(int i=m;i>=1;i--)
        if(f[1][i]>=0)
        {
            printf("%d",i);
            break;
        }
    return 0;
}

后记（fei hua）

为方便个人统计需要，

如果您看懂了，请点赞；

如果您想一想后懂了，请点赞；

如果您没看懂，请在讨论区里问。