POJ 1155 - TELE

http://poj.org/problem?id=1155

概要

N 個のノードからなる木で表現されたテレビネットワークが与えられる．

M 個の葉ノードはユーザを表し，そのユーザに配信すると price[i] の収入を得ることができる．

葉ノード以外のノードは送信機を表し，各エッジにはコストが設定されており，そのエッジを使うにはそのコストを払わなければならない．

このとき，利益が負にならない最大のユーザ数を答える．

制約

解法

dp[n][m] = ノード n より下で m 人に配信したときの最大の利益 という DP 表を葉ノードから埋めていき，dp[N][i] が非負であるような最大の i を答えればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int N, M;
 7 vector<vector<pair<int,int> > > g;
 8 int dp[3000][3000];
 9 int price[3000];
10 
11 int dfs(int n)
12 {
13   if (n < N-M) {
14     // transmitter
15     dp[n][0] = 0;
16     int cnt = 0;
17     for (vector<pair<int,int> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
18       const int a = it->first;
19       const int c = it->second;
20       const int r = dfs(a);
21       static int tmp[3000];
22       copy(dp[n], dp[n]+cnt+1, tmp);
23       for (int i = 0; i <= cnt; i++) {
24         for (int j = r; j > 0; j--) {
25           dp[n][i+j] = max(dp[n][i+j], tmp[i] + dp[a][j] - c);
26         }
27       }
28       cnt += r;
29     }
30     return cnt;
31   } else {
32     // user
33     dp[n][0] = 0;
34     dp[n][1] = price[n];
35     return 1;
36   }
37 }
38 
39 int main()
40 {
41   scanf("%d %d", &N, &M);
42   g.resize(N);
43   for (int i = 0; i < N-M; i++) {
44     int K;
45     scanf("%d", &K);
46     for (int j = 0; j < K; j++) {
47       int A, C;
48       scanf("%d %d", &A, &C);
49       --A;
50       g[i].push_back(make_pair(A, C));
51     }
52   }
53   for (int i = 0; i < M; i++) {
54     scanf("%d", &price[N-M+i]);
55   }
56 
57   for (int i = 0; i < N; i++) {
58     for (int j = 0; j <= M; j++) {
59       dp[i][j] = -10000000;
60     }
61   }
62   dfs(0);
63   for (int i = M; i >= 0; i--) {
64     if (dp[0][i] >= 0) {
65       printf("%d\n", i);
66       break;
67     }
68   }
69   return 0;
70 }
poj/1155.cc