首页 > 代码库 > POJ 1155 TELE

POJ 1155 TELE

2024-07-14 19:23:55   223人阅读

题目意思：
　　电视台发送信号给很多用户，每个用户愿意出一些钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。
多么明显的有依赖性的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;}

 


联系
我们