洛谷1273：有线电视网——题解

https://www.luogu.org/problemnew/show/P1273

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

总觉得可以用O(n^2)的复杂度算这道题，比如HDU1561：The more, The Better一样，但是我太菜了，如果有做出来的同学请不吝赐教。

O(n^3)我感觉有点别扭，就在于你定义的dp[i][j]表示以i为根取j个叶子的最大收益，这样我们只需要枚举j判断dp[1][j]就知道是否合法了。

转移方程和HDU1561：The more, The Better的O(n^3)大体一样，就不细讲了。

注意对于这个更新点的点权要在它所有的东西都更新完了之后再更新进去。

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=3010;
const int INF=1e9;
inline int read(){
int X=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
struct node{
int to,nxt;
}e[N];
int cnt,head[N],minn=0,maxn=0;
int n,m,c[N],son[N],dp[N][N];
inline void add(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void dfs(int u){
if(!head[u]){
dp[u][1]=c[u];son[u]=1;return;
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dfs(v);
son[u]+=son[v];
for(int j=son[u];j>=0;j--){
for(int k=0;k<=j;k++){
dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);
}
}
}
for(int j=son[u];j>=0;j--){
dp[u][j]+=c[u];
}
}
int main(){
n=read(),m=read();
for(int u=1;u<=n-m;u++){
int k=read();
for(int j=1;j<=k;j++){
int v=read();c[v]=-read();
add(u,v);
}
}
for(int u=n-m+1;u<=n;u++)c[u]+=read();
for(int u=1;u<=n;u++)
for(int j=1;j<=m;j++)
dp[u][j]=-INF;
dfs(1);
for(int i=m;i>=0;i--){
if(dp[1][i]>=0){
printf("%dn",i);
return 0;
}
}
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++