洛谷P1273 有线电视网

发表于 | 分类于
字数统计: 314 | 阅读时长 ≈ 2

记为i 节点，取j 个能获得的最大收入
叶节点
转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<vector>
using namespace std;
const int N=3050,rt=1,INF=1<<20;
int dp[N][N],n,m,sz[N];
vector<int> e[N],g[N];
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int u,int v,int val)
{
    e[u].push_back(v);
    g[u].push_back(val);
}
void dfs(int o)
{
    if (o>n-m) sz[o]=1;
    for(int k=0;k<e[o].size();k++)
    {
        int to=e[o][k];
        dfs(to);
        for(int i=m;i>=0;i--)
            for(int j=0;j<=min(i,sz[to]);j++)
                dp[o][i]=max(dp[o][i],dp[o][i-j]+dp[to][j]-g[o][k]);
        sz[o]+=sz[to];
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n-m;i++)
    {
        int T=read();
        while (T--)
        {
            int u=i,v=read();
            add(u,v,read());
        }
    }
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++) dp[i][j]=-INF;
    for(int i=n-m+1;i<=n;i++) dp[i][1]=read();
    dfs(rt);
    for(int i=m;i>=0;i--)
        if (dp[rt][i]>=0) 
        {
            printf("%d\n",i);
            return 0;
        }
    return 0;
}