POJ 1155 TELE(트리 DP)

1718 단어
제목: 한 텔레비전 방송국의 방송 프로그램이 있는데 방송의 네트워크는 한 그루의 나무로 표시한다. 노드 1은 방송국을 표시하고 잎사귀 결점은 사용자를 표시한다. 사용자는 일정한 돈을 지불하고 이 프로그램을 시청하고 싶어 한다. 비잎사귀 결점에서 다른 결점까지 일정한 비용(즉 중계점에서 다른 중계점까지 약간의 돈이 필요하다)이 필요하다. 마지막에 손해를 보지 않는 상황에서 최대 몇 명이 프로그램을 볼 수 있느냐고 묻는다.
정의 dp[i][j]는 노드 i가 뿌리 노드인 하위 나무 아래에서 j 개인이 노드를 시청하는 최대 이윤을 나타낸다.
상태 이동 방정식은 dp[i][j]=max(dp[i][j], dp[i][j-k]+dp[son of i][k])
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF (1<<30)
const int N=3005;
struct Edge
{
	int v,w;
	Edge* nxt;
}memo[N*N],*cur,*adj[N];

int dp[N][N],n,m;
int num[N];

void addEdge(int u,int v,int w)
{
	cur->v=v; cur->w=w;
	cur->nxt=adj[u];
	adj[u]=cur++;
}
void dfs(int u,int fa)
{
	for(Edge* it=adj[u];it;it=it->nxt)
	{
		int v=it->v,w=it->w;
		if(v==fa) continue;
		dfs(v,u);
		num[u]+=num[v];
		for(int i=num[u];i>=0;i--)
			for(int j=0;j<=i;j++)
				if(dp[u][i-j]!=-INF&&dp[v][j]!=-INF) 
					dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v][j]-w);
	}
}
void init()
{
	cur=memo;
	memset(adj,0,sizeof(adj));
	memset(num,0,sizeof(num));
	for(int i=0;i<=n;i++)
	{
		dp[i][0]=0;
		for(int j=1;j<=m;j++) dp[i][j]=-INF;
	}
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();

		int v,w,k;
		for(int i=1;i<=n-m;i++)
		{
			scanf("%d",&k);
			for(int j=0;j<k;j++)
			{
				scanf("%d%d",&v,&w);
				addEdge(i,v,w);
				addEdge(v,i,w);
			}
		}
		for(int i=n-m+1;i<=n;i++) 
			scanf("%d",&dp[i][1]),num[i]=1;

		dfs(1,-1);
		for(int i=m;i>=0;i--)
		{
			if(dp[1][i]>=0)
			{
				printf("%d
",i); break; } } } return 0; }

좋은 웹페이지 즐겨찾기