P1273?有线电视网
https://www.luogu.com.cn/problem/P1273
?很好的一题
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int MAXN=1e6+10;
using ll=long long;
int head[MAXN];
int nxt[MAXN];
int ver[MAXN];
int cost[MAXN];
int cnt;
int n,m;
int val[MAXN];
inline void add(int x,int y,int c){
ver[++cnt]=y;
nxt[cnt]=head[x];
cost[cnt]=c;
head[x]=cnt;
}
int f[5000][5000];
int dfs(int p){
if(p>n-m){
f[p][1]=val[p];
return 1;
}
int sum=0,t;
for(int i=head[p];i;i=nxt[i]){
int v=ver[i];
t=dfs(v);
sum+=t;
for(int j=sum;j;j--){
for(int k=1;k<=t;k++){
if(j>=k){
f[p][j]=max(f[p][j],f[p][j-k]+f[v][k]-cost[i]);
}
}
}
}
return sum;
}
int main(){
memset(f,128,sizeof(f));
scanf("%d %d",&n,&m);
for(int i=1,t,x,y;i<=n-m;i++){
scanf("%d",&t);
for(int j=1;j<=t;j++){
scanf("%d %d",&x,&y);
add(i,x,y);
}
}
for(int i=n-m+1;i<=n;i++){
scanf("%d",val+i);
}
for(int i=1;i<=n;i++){
f[i][0]=0;
}
dfs(1);
for(int i=m;i;i--){
if(f[1][i]>=0){
printf("%d",i);
break;
}
}
return 0;
}
