題面:https://www.luogu.org/problem/P1273

本題是樹上背包裸題。Code: #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<ctime> using namespace std; const int N=3005; int n,m,Head[N],Cnt,pay[N],f[N][N]; struct node{int u,v,Next,w; }Edge[N*2]; void Push(int u,int v,int w){++Cnt;Edge[Cnt].u=u;Edge[Cnt].v=v;Edge[Cnt].w=w;Edge[Cnt].Next=Head[u];Head[u]=Cnt; } int dfs(int u){if(u>n-m){f[u][1]=pay[u];return 1;}int size=0,t;for(int i=Head[u];i;i=Edge[i].Next){int v=Edge[i].v;t=dfs(v);size+=t;for(int j=size;j>0;j--){for(int k=1;k<=t;k++){if(j-k>=0){f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-Edge[i].w);}}}}return size; } int main(){memset(f,-0x3f,sizeof(f));scanf("%d%d",&n,&m);for(int u=1;u<=n-m;u++){int k,v,w;scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d%d",&v,&w);Push(u,v,w);}}for(int i=n-m+1;i<=n;i++){scanf("%d",&pay[i]);}for(int i=1;i<=n;i++){f[i][0]=0;}dfs(1);for(int i=m;i>=1;i--){if(f[1][i]>=0){printf("%d\n",i);return 0;}}return 0; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11243584.html

總結

以上是生活随笔為你收集整理的P1273 有线电视网的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。