1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <stdlib.h>
#include <string.h>
#define MAXN 222
int M,N;
int Tree[MAXN][MAXN];
int count[MAXN];
int visit[MAXN];
int value[MAXN];
int dp[MAXN][MAXN];
enum boolean {FALSE,TRUE};
int (int x,int y) { return x>y?x:y;}
int MAX(int x,int y) { return x<y?x:y;}
int DFS(int p)
{
int i,j,k,r;
visit[p] = TRUE;
for (i = 0; i <= count[p]; i++)
{
r = Tree[p][i];
if (visit[r]==FALSE)
DFS(r);
for (j = M; j>= 2; j--)
{
for (k = 1; k < j; k++)
{
if (dp[r][k]!=-1 && dp[p][j-k]!=-1)
dp[p][j] = MAX(dp[p][j],dp[p][j-k]+dp[r][k]);
}
}
return TRUE;
}
int main()
{
freopen("Sample Input.txt","r",stdin);
int i,p,j;
while (scanf("%d%d",&M,&N),M||N)
{
memset(count,-1,sizeof(count));
for (i = 1; i <= N; i++)
{
scanf("%d%d",&p,&value[i]);
Tree[p][++count[p]] = i;
dp[i][1] = value[i];
}
dp[0][1] = 0;
for (i = 0; i <= N; i++)
{
dp[i][0] = 0;
for (j = 2; j <= M; j++)
dp[i][j] = -1;
visit[i] = FALSE;
}
M++;
DFS(0);
printf("%dn",dp[0][M]);
}
getch();
return 0;
}
|
近期评论