所以可以求一个40分抓虫吗

回复帖子

@REM_001 2019-04-14 20:14 回复

#include<bits/stdc++.h>
using namespace std;
int kl,kll,head[100000],n,x,y,tot,sum,z,k,m,father[100000],DFN[1000001],LOW[100001],w[100001];
int disw[1000001],disv[100001],dis[100001],stac[100001],vis[100001],f[1001][1001],indec,v[100001];
bool b_dfs[100000],visit[100001]; 
struct line{int fr,to,next,data,last;}q[1000000],edge[1000001];
void pushline(int f,int t)
{   
    q[++kl].next=head[f];
    q[kl].fr=f,q[kl].to=t;
    head[f]=kl;
}
void pushsec(int f,int t)
{
    edge[++kll].next=head[f];
    edge[kll].to=t;
    head[f]=kll;
}
void tarjan(int x)
{
    DFN[x]=LOW[x]=++tot;
    stac[++indec]=x;
    visit[x]=1;
    for(int i=head[x];i!=0;i=q[i].next)
    {
        if(!DFN[q[i].to]) 
        {
            tarjan(q[i].to);
             LOW[x]=min(LOW[x],LOW[q[i].to]);
        }
        else if(visit[q[i].to])LOW[x]=min(LOW[x],DFN[q[i].to]);
    }
    if(LOW[x]==DFN[x])
    {
        sum++;
        do{
        vis[stac[indec]]=sum;
        disw[tot]+=w[stac[indec]]; 
        disv[tot]+=v[stac[indec]];
        visit[stac[indec]]=0;
        indec--;
        }while(x!=stac[indec+1]);
    }
    return;
}
void dfs(int x)
{
    for(int i=disw[x];i<=m;i++)f[x][i]=disv[x];
    for(int p=head[x];p!=0;p=edge[p].next)
    {
        int u=edge[p].to;
        dfs(u);
        for(int j=m-disw[x];j>=0;j--)
        {
            for(int k=0;k<=j;k++)
            {
                f[x][j+disw[x]]=max(f[x][j+disw[x]],f[x][j+disw[x]-k]+f[u][k]);
            }
        }   
    }

}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=n;i++)cin>>v[i];
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        pushline(x,i);
    }
    memset(head,0,sizeof(head));
    for(int i=1;i<=n;i++)if(!DFN[i])tarjan(i);
    for(int i=1;i<=kl;i++)
    {
        int u=vis[q[i].fr],v=vis[q[i].to];
        if(u!=v)pushsec(u,v);
    } 
    dfs(0);
    cout<<f[0][m];

} 
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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