萌新刚学OI,莫名40分,求助

回复帖子

@KevinYu 2018-11-28 17:59 回复
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<ctime>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
struct edge
{
    int to,next;
}a[2020],dag[2020];
int hag[2020];
int head[2020];
int w[2020];
int c[2020];
int p[2020];
int e[2020];
int f[2020][3030];
int low[2020];
int dfn[2020];
int now(0);
int hep[2020];
int top(0);
int vis[2020];
int fa[2020];
int cnt(0);
int cal(0);
int tot(0);
int n,m;
void addedge(int xi,int yi)
{
    a[cnt].to=yi;
    a[cnt].next=head[xi];
    head[xi]=cnt++;
}
void addag(int xi,int yi)
{
    dag[cal].to=yi;
    dag[cal].next=hag[xi];
    hag[xi]=cal++;
}
void tarjan(int u)
{
    low[u]=dfn[u]=++now;
    hep[++top]=u;
    vis[u]=1;
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;
        if(!dfn[v]){tarjan(v);low[v]=min(low[u],low[v]);}
        else if(vis[v])low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        tot++;
        while(hep[top+1]!=u)
        {
            fa[hep[top]]=tot;
            vis[hep[top--]]=0;
        }
    }
}
void dfs(int u)
{
    for(int i=p[u];i<=m;i++)f[u][i]=e[u];
    for(int i=hag[u];i!=-1;i=dag[i].next)
    {
        int v=dag[i].to;
        dfs(v);
        for(int j=m-p[u];j>=0;j--)
        {
            for(int k=0;k<=j;k++)
            {
                f[u][j+p[u]]=max(f[u][j+p[u]],f[u][j+p[u]-k]+f[v][k]);
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(hag,-1,sizeof(hag));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(x==0)x=n+1;
        addedge(x,i);
    }
    tarjan(n+1);
    for(int u=0;u<=n+1;u++)
    {
        p[fa[u]]+=c[u];
        e[fa[u]]+=w[u];
        for(int i=head[u];i!=-1;i=a[i].next)
        {
            if(fa[u]!=fa[a[i].to])addag(fa[u],fa[a[i].to]);
        }
    }
    p[n+1]=0;
    e[n+1]=0;
    dfs(fa[n+1]);
    printf("%d",f[fa[n+1]][m+p[n+1]]);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。