一道树形背包。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=6e3+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct edge{int y,next,d;}a[N<<1];int len,last[N];
void ins(int x,int y,int d){a[++len]=(edge){y,last[x],d};last[x]=len;}
int f[N][3005],c[N];int n,m;
void dfs(int x,int fa)
{
c[x]=1;
for(int k=last[x],y;k;k=a[k].next)
{
y=a[k].y;if(y==fa)continue;
dfs(y,x);
c[x]+=c[y];
for(int i=min(c[x],m);i;i--)
{
int mn=min(i,c[y]);
for(int j=mn;j;j--)
f[x][i]=max(f[x][i],f[x][i-j]+f[y][j]+a[k].d);
}
}
}
int main()
{
qr(n),qr(m);
for(int i=1;i<=n-m;i++)
{
int k;qr(k);
for(int j=1,y,d;j<=k;j++)
qr(y),qr(d),ins(i,y,-d);
}
memset(f,0xcf,sizeof(f));
for(int i=1;i<=n-m;i++)f[i][0]=0;
for(int i=n-m+1;i<=n;i++)
qr(f[i][1]),f[i][0]=0;
dfs(1,0);
for(int i=m;i>=0;i--)if(f[1][i]>=0){printf("%d\n",i);return 0;}
return 0;
}
最后一次更新于2020-05-13
0 条评论