The more, The Better HDU - 1561

​​http://acm.hdu.edu.cn/showproblem.php?pid=1561​​

先正向拓撲去掉無法到達的點 然後用剩下的點建一正一反兩個圖

然後逆向拓撲 當某點因度數為0而入隊列時 說明正向圖中他的所有後繼節點（即從該點進行BFS能到達的所有點）都已周遊 這和樹型DP的思想一樣 隻不過這裡需要考慮的拓撲序稍複雜一些

這時可以想到利用01分組背包的思想 dp[i][j]代表從第i個節點出發攻占至多j個節點的最大收益 即對要入隊列的節點v 周遊其正向圖中所有後繼節點w 每個節點w的dp[w][1] dp[w][2]...dp[w][m]都當做一樣物品且每樣隻有一件 這就是01背包 又因為每樣物品互相沖突 這又是分組背包

還有要注意的是 因為除了虛根0之外 每個節點v在計算dp[v][i]時都要保證包含本身節點 詳見代碼

最後 我孫雨田現在也能寫出正兒八經的DP題了！！！（發現其實是自己想麻煩了而已）

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e2+10;

struct node
{
    int v,next;
};

queue <int> que;
node edge1[maxn],edge2[maxn];
int dp[maxn][maxn];
int first1[maxn],first2[maxn],degree[maxn],pre[maxn],val[maxn],book[maxn];
int n,m,num1,num2;

void addedge(node* edge,int* first,int u,int v,int &num)
{
    edge[num].v=v;
    edge[num].next=first[u];
    first[u]=num++;
}

void toposort()
{
    int i,u,v;
    while(!que.empty()) que.pop();
    memset(book,0,sizeof(book));
    que.push(0);
    book[0]=1;
    while(!que.empty()){
        u=que.front();
        que.pop();
        for(i=first1[u];i!=-1;i=edge1[i].next){
            v=edge1[i].v;
            degree[v]--;
            if(degree[v]==0){
                que.push(v);
                book[v]=1;
            }
        }
    }
}

void rebuild()
{
    int u;
    memset(first1,-1,sizeof(first1));
    memset(first2,-1,sizeof(first2));
    memset(degree,0,sizeof(degree));
    num1=0,num2=0;
    for(u=1;u<=n;u++){
        if(book[u]&&book[pre[u]]){
            addedge(edge1,first1,pre[u],u,num1);
            addedge(edge2,first2,u,pre[u],num2);
            degree[pre[u]]++;
        }
    }
}

int solve()
{
    int tmp[maxn];
    int i,j,k,l,p,u,v,w;
    memset(dp,0,sizeof(dp));
    while(!que.empty()) que.pop();
    for(i=1;i<=n;i++){
        if(degree[i]==0){
            que.push(i);
            for(j=1;j<=m;j++){
                dp[i][j]=val[i];
            }
        }
    }
    while(!que.empty()){
        u=que.front();
        que.pop();
        for(i=first2[u];i!=-1;i=edge2[i].next){
            v=edge2[i].v;
            degree[v]--;
            if(degree[v]==0){
                //printf("***%d***\n",v);
                que.push(v);
                for(l=1;l<=m;l++){
                    dp[v][l]=val[v];
                }
                for(j=first1[v];j!=-1;j=edge1[j].next){
                    w=edge1[j].v;
                    //printf("*%d*\n",w);
                    for(l=1;l<=m;l++) tmp[l]=dp[v][l];
                    //for(l=1;l<=m;l++) printf("%d ",tmp[l]);
                    //printf("\n");
                    for(k=1;k<=m;k++){
                        //printf("^%d^\n",k);
                        if(v==0) p=k;
                        else p=k+1;
                        for(l=m;l>=p;l--){
                            //printf("%d %d\n",dp[v][l-k],dp[w][k]);
                            tmp[l]=max(tmp[l],dp[v][l-k]+dp[w][k]);
                        }
                    }
                    //for(l=1;l<=m;l++) printf("%d ",tmp[l]);
                    //printf("\n");
                    for(l=1;l<=m;l++) dp[v][l]=max(dp[v][l],tmp[l]);
                }

            }
        }
    }
    /*
    for(i=0;i<=n;i++){
        printf("***%d***\n",i);
        for(j=0;j<=m;j++){
            printf("%d ",dp[i][j]);
        }
        printf("\n");
    }
    */
    return dp[0][m];
}

int main()
{
    int u;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0) break;
        memset(first1,-1,sizeof(first1));
        memset(degree,0,sizeof(degree));
        num1=0;
        for(u=1;u<=n;u++){
            scanf("%d%d",&pre[u],&val[u]);
            addedge(edge1,first1,pre[u],u,num1);
            degree[u]++;
        }
        toposort();
        rebuild();
        printf("%d\n",solve());
    }
    return 0;
}