洛谷 P1273 有线电视网

本文主要是介绍洛谷 P1273 有线电视网，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

洛谷 P1273 有线电视网

题目分析

本蒟一开始想的是这样的方程:dp[i][j]表示的是当前i节点时花费了j所取得的最大用户数
更新时这样更新:dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son[i]][k]);
每个用户节点的初始值为1.但是好像这样不行?不晓得怎么控制循环转移
于是看了网上大佬的题解,发现是这样讲的dp[i][j]是第i个节点转播给j个用户的最大收益,只要在最后判断的时候,从n到n-m+1时是否有大于等于0的收益即可输出答案

程序代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct arr{int nd,nx,co;
}bot[6115];
int n,m,cnt;
int head[3005],vis[3005],du[3005];
int f[3005][3005];
inline int read(){int x=0,w=1;char ch;while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') w=-1,ch=getchar();while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();return x*w;
}
inline void add(int a,int b,int c){ bot[++cnt].nd=b; bot[cnt].nx=head[a]; bot[cnt].co=c; head[a]=cnt; }
void dfs(int u) {vis[u]=1;for(register int i=head[u];i;i=bot[i].nx) {int v=bot[i].nd;if(!vis[v]) {dfs(v);du[u]+=du[v];for(register int j=du[u];j>=1;--j)for(register int k=0;k<=j;++k)f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-bot[i].co);}}
}
int main(){freopen("P1273.in","r",stdin);freopen("P1273.out","w",stdout);n=read();m=read();for(register int i=1;i<=n;++i)for(register int j=1;j<=n;++j)f[i][j]=-0x3f3f3f3f;//注意要赋初始值,初始值不能是0for(register int i=1;i<=n-m;++i) {int k=read();for(register int j=1;j<=k;++j) {int x=read(),y=read();add(i,x,y);add(x,i,y);}}for(register int i=n-m+1;i<=n;++i) {f[i][1]=read();du[i]=1;}dfs(1);for(register int i=du[1];i>=1;--i){if(f[1][i]>=0) {printf("%d\n",i);break;}}return 0;
}