首页 > 代码库 > poj 1155 TELE
poj 1155 TELE
题意：一个电视台想要播出某足球节目，有n个点,1号为电视台，前m个为中转站，后面的为用户，所有点之间是树形结构，建设线路需要一定费用，每个用户愿意缴纳ai，求在不亏损的情况下，最多能让多少用户收看节目
很显然的树dp,接下来的工作就是推出怎么状态和状态转移方程因为要保证不会亏损，那么dp记录的肯定是剩余的花费，如果dp[u][i]表示以u为根节点的子树有i个用户的最大剩余花费，那么问题就迎刃而解，答案就是dp[1][i]中i最大
的dp[1][i]>=0的，就是答案状态转移方程也不难
for(int i=tsize[u];i>=0;i--)
for(int j=0;j<=i;j++)
if(dp[v][j]!=-INF&&dp[u][i-j]!=-INF)
dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v][j]-w);
#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<cstdio>using namespace std;const int maxn=3005;const int INF=0x3f3f3f3f;vector<int> g[maxn],val[maxn];int dp[maxn][maxn],tsize[maxn];int n,m;void init(){ memset(dp,-INF,sizeof(dp)); for(int i=0;i<=n;i++)dp[i][0]=0; for(int i=0;i<=n;i++)g[i].clear(),val[i].clear();}void dfs(int u,int f){ tsize[u]=1; for(int i=0;i<g[u].size();i++){ int v=g[u][i],w=val[u][i]; if(v==f)continue; dfs(v,u); tsize[u]+=tsize[v]; for(int i=tsize[u];i>=0;i--) for(int j=0;j<=i;j++) if(dp[v][j]!=-INF&&dp[u][i-j]!=-INF) dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v][j]-w); }}int main(){ //freopen("in","r",stdin); ios::sync_with_stdio(false); while(cin>>n>>m){ init(); for(int i=1;i<=n-m;i++){ int u,v,w;cin>>u; while(u--){ cin>>v>>w; g[v].push_back(i);g[i].push_back(v); val[v].push_back(w);val[i].push_back(w); } } for(int i=n-m+1;i<=n;i++)cin>>dp[i][1]; dfs(1,-1); int ans; for(int i=n;i>=0;i--) if(dp[1][i]>=0){ans=i;break;} cout<<ans<<endl; } return 0;}
poj 1155 TELE
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。