TELE
题目:http://poj.org/problem?id=1155
题意:一个电视信号传输网络(树),点1为信号源,图中有N个点,其中包括M个用户和N-M个传输点(包括1),铺设点与点之间的线需要一定的钱,每个用户也会对电视信号付出一些钱,问怎样建设网络可以使尽可能多的用户收到信号且电视台不亏本。
题解:树形DP和背包,dp[i][j]为第i个点给j个用户传输信号的最大收益,dp初始化为最小值。
ps:竟然1A了,惊喜啊。
代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 3005 #define inf 0xfffff int edge[MAX];//表示第i条边的终点 int next[MAX];//与第i条边同起点的下一条边的位置 int head[MAX];//以i为起点的第一条边的储存位置 int cost[MAX];//第i条边的权值 int value[MAX];//第i个点的权值 int dp[MAX][MAX]; int cnt; void insert(int a,int b,int c)//a起点,b终点 { edge[++cnt]=b; next[cnt]=head[a]; head[a]=cnt; cost[cnt]=c; } int dfs(int x) { int summ=0; dp[x][0]=0; int t[MAX]; bool flag=false; for(int i=head[x]; i!=-1; i=next[i]) { flag=true; t[edge[i]]=dfs(edge[i]); summ+=t[edge[i]]; } for(int i=head[x]; i!=-1; i=next[i]) { int k=edge[i]; for(int j=summ; j>=0; --j) { if(dp[x][j]==-inf) continue; for(int q=1; q<=t[k]; ++q) dp[x][j+q]=max(dp[x][j+q],dp[x][j]+dp[k][q]-cost[i]);//根结点取j个用户,子结点k取q个用户 } } if(flag) return summ; else//当前结点为用户 { dp[x][1]=value[x]; return 1; } } int main() { int n,m,k,b,c; for(; ~scanf("%d%d",&n,&m);) { memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next)); cnt=0; for(int i=1; i<=n-m; ++i) { scanf("%d",&k); for(; k--;) { scanf("%d%d",&b,&c); insert(i,b,c); } } for(int i=n-m+1; i<=n; ++i) scanf("%d",&value[i]); for(int i=1; i<=n-m; ++i) for(int j=0; j<=m; ++j) dp[i][j]=-inf; dfs(1); int ans=0; for(int i=m; i>=0; --i) if(dp[1][i]>=0) { ans=i; break; } printf("%d\n",ans); } return 0; }