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
58
59
| #include<bits/stdc++.h>
using namespace std;
struct Edge{
int v,w,nxt;
}mem[3005*2];
int head[3005],cnt;
int size[3005];
inline void AddEdge(int u,int v,int w){
mem[++cnt].v=v;
mem[cnt].w=w;
mem[cnt].nxt=head[u];
head[u]=cnt;
}
int N,M;
int leaf[3005];
int f[3005][3005];
inline void dfs(int u){
if(leaf[u]){
f[u][1]=leaf[u];
size[u]=1;
return;
}
for(register int i=head[u];i;i=mem[i].nxt){
int v=mem[i].v,w=mem[i].w;
dfs(v);
size[u]+=size[v];
for(register int j=M;j>=1;--j)
for(register int k=0;k<=min(size[v],j);++k)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w);
}
}
int main(){
memset(f,0xcf,sizeof(f));
scanf("%d%d",&N,&M);
for(register int i=1;i<=N-M;++i){
int k;
scanf("%d",&k);
for(register int j=1;j<=k;++j){
int a,c;
scanf("%d%d",&a,&c);
AddEdge(i,a,c);
}
}
for(register int i=1;i<=M;++i) scanf("%d",&leaf[N-M+i]);
for(register int i=1;i<=N;++i) f[i][0]=0;
dfs(1);
for(register int i=M;i>=1;--i){
if(f[1][i]>=0){
printf("%d",i);
return 0;
}
}
return 0;
}
|