洛谷P1273 有线电视网题解

题意：

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

如果直接去想怎么保证不超过边权和什么的不太好搞

考虑把每个用户数是否能够承担都算出来即可

也就是

设 $dp[i][u][j]$ 表示以 $u$ 为根的子树，仅用前 $i$ 个儿子，满足 $j$ 个客户能获得的最大价值

事实上我们并不是非常关心是否能获得的最大价值，我们只要不亏本的情况下尽可能多让人看罢了（~~好良心有没有~~）

则有转移方程

$dp[i][u][j]=\max(dp[i][u][j],dp[i-1][u][j-k]+dp[\text{sz}[v]][v][k]-w(u,v))$

可以发现这个东西可以滚动数组优化

然后就有

$dp[u][j]=\max(dp[u][j],dp[u][j-k]+dp[v][k]-w(u,v))$

sz[u]+=sz[v];
for(int j=sz[u]; j>=0; j--)
    for(int k=1; k<=min(sz[v],j); k++)
        dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-e[i].w);

AC？不，这样会TLE。参考讨论 link

因为这样的复杂度并不能保证为严格 $O(n^2)$ 的，这也就是所谓的实现不好。

改成下面的刷表法就好了

$dp[u][j+k]=\max(dp[u][j+k],dp[u][j]+dp[v][k]-w(u,v))$

for(int j=0; j<=sz[u]; j++)
    tmp[j]=dp[u][j];
for(int j=0; j<=sz[u]; j++)
    for(int k=0; k<=sz[v]; k++)
        dp[u][j+k]=max(dp[u][j+k],tmp[j]+dp[v][k]-e[i].w);

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(3e3+15)

int n,m,dp[N][N];
struct Edge
{
    int u,v,w,next;
}e[N<<1];
int pos=1,head[N],sz[N],val[N],tmp[N];
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void dfs(int u,int f)
{
    sz[u]=1;
    if(u>n-m) dp[u][1]=val[u];
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        dfs(v,u);
        //AC
        for(int j=0; j<=sz[u]; j++)
            tmp[j]=dp[u][j];
        for(int j=0; j<=sz[u]; j++)
            for(int k=0; k<=sz[v]; k++)
                dp[u][j+k]=max(dp[u][j+k],tmp[j]+dp[v][k]-e[i].w);
        sz[u]+=sz[v];
        // TLE
        // sz[u]+=sz[v];
        // for(int j=sz[u]; j>=0; j--)
        //     for(int k=1; k<=min(sz[v],j); k++)
        //         dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-e[i].w);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n-m; i++)
    {
        int k;cin >> k;
        for(int j=1,v,w; j<=k; j++)
        {
            cin >> v >> w;
            addEdge(i,v,w);
            addEdge(v,i,w);
        }
    }
    for(int i=n-m+1; i<=n; i++)
        cin >> val[i];
    memset(dp,0xc0,sizeof(dp));
    for(int i=1; i<=n; i++)
        dp[i][0]=0;
    dfs(1,1);
    for(int i=m; i>=0; i--)
        if(dp[1][i]>=0)return cout << i,0;
    return 0;
}