POJ 1155 TELE(트리 DP)

제목:
한 텔레비전 방송국의 방송 프로그램이 있는데 방송의 네트워크는 한 그루의 나무로 표시한다. 노드 1은 방송국을 표시하고 잎사귀 결점은 사용자를 표시한다. 사용자는 일정한 돈을 지불하고 이 프로그램을 시청하고 싶어한다.
비엽자결점에서 다른 결점까지 일정한 비용(즉 중계점에서 다른 중계점까지 약간의 돈이 필요하다)이 필요하고, 마지막에 손해를 보지 않은 상황에서 최대 몇 명이 프로그램을 볼 수 있느냐고 물었다.
아이디어:
1. POJ 1947과 유사한 제목으로 dp[u][i]는 u 노드를 뿌리로 하고 i 노드의 최대 이윤을 보존한다.
2. dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j] - w)
3. 잎 노드가 선정되면 잎에서 뿌리까지의 한 경로 위의 노드가 모두 선정되어야 하기 때문에 초기화할 때 부치는 -INFS이고 dp[잎][i]가 합법적일 때만 dp[rt][]가 합법적이다.
4.sum[u]는 u를 루트로 하는 하위 트리가 몇 명의 유효한 사용자를 덮어쓸 수 있는지 나타낸다.문제 풀이의 최적화라고 할 수 있다.
 

#include <iostream>

#include <algorithm>

using namespace std;



const int MAXN = 3010;

const int INFS = 0x3fffffff;



structedge {

    int v, c;

    edge* next;

} *V[MAXN], ES[MAXN * 3];



int EC, N, M, sum[MAXN], dp[MAXN][MAXN];



void addedge(int u, int v, int c)

{

    ES[++EC].next = V[u];

    V[u] = ES + EC; 

    V[u]->v = v, V[u]->c = c;

}



void initdata()

{

    for (int i = 1; i <= N; ++i)

    {

        dp[i][0] = 0;

        for (int j = 1; j <= M; ++j)

            dp[i][j] = -INFS;

    }



    EC = 0;

    memset(V, 0, sizeof(V));



    for (int i = 1; i <= N - M; ++i)

    {

        int k, a, b;

        scanf("%d", &k);

        for (int j = 0; j < k; ++j)

        {

            scanf("%d %d", &a, &b);

            addedge(i, a, b);

            addedge(a, i, b);

        }

    }



    memset(sum, 0, sizeof(sum));

    for (int i = N - M + 1; i <= N; ++i)

        scanf("%d", &dp[i][1]), sum[i] = 1;

}



void treedp(int u, int f)

{

    for (edge* e = V[u]; e; e = e->next)

    {

        if (e->v == f)

            continue;



        treedp(e->v, u);

        sum[u] += sum[e->v];



        for (int i = sum[u]; i >= 1; --i)

            for (int j = 1; j <= i; ++j)

                if (dp[u][i-j] != -INFS && dp[e->v][j] != -INFS)

                    dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[e->v][j] - e->c);

    }

}



int main()

{

    while (scanf("%d %d", &N, &M) != EOF)

    {

        initdata();

        treedp(1, 0);



        int i;

        for (i = M; i >= 0; --i)

            if (dp[1][i] >= 0)

                break ;



        printf("%d
", i);

    }

    return 0;

}