首页 > 代码库 > POJ 1155 TELE
POJ 1155 TELE
题目意思:
电视台发送信号给很多用户,每个用户愿意出一些钱,电视台经过的路线都有一定费用,求电视台不损失的情况下最多给多少用户发送信号。
多么明显的有依赖性的01背包:
dp[i][j]对于借点I 背包容量J ;
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <cstdlib>using namespace std;const int maxn=3004;const int INF=0x7ffffff;struct Edge{ int to,dis,pre; Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){}};Edge edge[maxn];int head[maxn],pos;int money[maxn];int dp[maxn][maxn];void inint(){ memset(head,-1,sizeof(head)); pos=0;}void add_edge(int &s,int &to,int &dis){ edge[pos]=Edge(to,dis,head[s]); head[s]=pos++;}int n,m;int dfs(int s){ int ans=0,key; dp[s][0]=0; for(int i=1;i<maxn;i++)dp[s][i]=-INF; for(int i=head[s];i!=-1;i=edge[i].pre) { Edge &tmp=edge[i]; if(tmp.to==-1) key=0; else key=dfs(tmp.to); ans+=key; for(int j=ans;j>=1;j--) for(int t=1;t<=key;t++) { if(j<t)break; dp[s][j]=max(dp[s][j],dp[s][j-t]+dp[tmp.to][t]-tmp.dis); } } if(s>(n-m)) { ans++; for(int j=ans;j>=1;j--) dp[s][j]=dp[s][j-1]+money[s]; } return ans;}int main(){ int num,a,b; while(~scanf("%d%d",&n,&m)) { inint(); for(int i=1;i<=(n-m);i++) { scanf("%d",&num); for(int w=1;w<=num;w++) scanf("%d%d",&a,&b), add_edge(i,a,b); } for(int i=n-m+1;i<=n;i++)scanf("%d",&money[i]); dfs(1); for(int i=n;i>=0;i--) if(dp[1][i]>=0){printf("%d\n",i);break;} } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。