题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

输入输出格式

输入格式：

 

第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)

接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。

 

输出格式：

 

只有一行，选M门课程的最大得分。

 

输入输出样例

输入样例#1： 复制

7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

输出样例#1： 复制

13


和二叉苹果树几乎一模一样  那题是边权  这题是点权


但是可能有多个子树  每个子树内的dp很简单  但是多个就。。。

仔细观察可得  所有的树都连在0点  所以答案就是dp[0][m+1]

以后也可以用这种方法  连一个超级源点

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=6000+5;
const int M=50005;
int head[M],pos;
struct Edge
{
    int nex,to,v;
}edge[M];
void add(int a,int b)
{
    edge[++pos].nex=head[a];
    head[a]=pos;
    edge[pos].to=b;
}
int n,m;
int dp[N][N];

void dfs(int u)
{
    for(int i=head[u];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        dfs(v);
        for(int j=m+1;j>=1;--j)
        for(int k=j-1;k>=1;--k )
        dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k] );
    }
}

int main()
{
    RII(n,m);
    rep(i,1,n)
    {
        int a,b;RII(a,b);
        add(a,i);
        dp[i][1]=b;
    }
    dfs(0);
    cout<<dp[0][m+1];
    return 0;
}

View Code