题目链接: http://poj.org/problem?id=1155
题目大意：电视台转播节目。对于每个根，其子结点可能是用户，也可能是中转站。但是用户肯定是叶子结点。传到中转站或是用户都要花钱，如果是用户，则还可以收钱。问在不亏本的前提下最多能有多少个用户看到节目。
解题思路：
比较麻烦的树形背包。首先cost=1。
花的钱权在边，收的钱权在点，且是叶子结点。所以首先可以对叶子结点进行预处理。
用dp[i][j]表示在i点时传播j个用户（包含自身），则dp[n-m-1~n][1]=每个用户缴费。
这样在dfs的时候就可以专心处理边权问题。两个for循环这么写：
for(f...j...cost)
for(0...k...j)
则转移方程就是dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]-e[a].w);
这里之所以是f而不是f+1，是因为中转站不是用户，不需要cost。f+=dfs(t)。
对于如何知道在不亏本的情况下的最多用户，在dfs之后，从dp[1][m..0]开始找一个大于0的最大m值。
如果你熟悉传统的树形背包的话，就会发现这里不能每次都使用最大背包容量m循环了，不然会TLE，原因是这题m比较大，每次都从m开始不T就怪了。
所以必须采用这种cost=1时特殊的当前最大容量f。
#include "cstdio"
#include "iostream"
#include "cstring"
using namespace std;
#define maxn 3005
#define inf 0x3f3f3f3f
struct Edge
{
int to,next,w;
}e[maxn];
int leaf[maxn],dp[maxn][maxn],get[maxn],head[maxn];
int n,m,k,v,w,tol;
void addedge(int u,int v,int w)
{
e[tol].to=v;
e[tol].next=head[u];
e[tol].w=w;
head[u]=tol++;
}
int dfs(int root)
{
if(head[root]==-) return ;
int i=root,f=,cost=;
for(int a=head[root];a!=-;a=e[a].next)
{
int t=e[a].to;
f+=dfs(t);
for(int j=f; j>=cost; j--)
for(int k=; k<=j; k++)
dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]-e[a].w);
}
return f;
}
int main()
{
//freopen("in.txt","r",stdin);
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<=n-m;i++)
{
scanf("%d",&k);
for(int j=;j<=k;j++)
{
scanf("%d%d",&v,&w);
addedge(i,v,w);
}
}
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
dp[i][j]=-inf;
for(int i=n-m+;i<=n;i++) {scanf("%d",&get[i]);dp[i][]=get[i];}
dfs();
for(int i=m;i>=;i--)
{
if(dp[][i]>=)
{
printf("%d\n",i);
break;
}
}
}
| 13540208 | neopenx | 1155 | Accepted | 33704K | 157MS | C++ | 1322B | 2014-10-18 00:48:42 |