对拍都拍不出错,交上去就wa 5,6两个点

回复帖子

@poaspoas 2019-04-22 12:00 回复
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define iinf 0x8f8f8f8f  
#define exp 1e-6;
#define max3(a,b,c) (max(max((a),(b)),(c)))
#define min3(a,b,c) (min(min((a),(b)),(c)))
#define ll long long
//#define mod 1000000007
using namespace std; 
template<class T>inline T cmin(T &a,T b){return a>b?a=b,1:0;} 
template<class T>inline T cmax(T &a,T b){return a<b?a=b,1:0;} 
const int N=10005;
int n,m,k,s,t,f[105][505],w[105],v[105],head[N],tot,ans;
int dfn[105],low[105],vis[105],dfs_num,col_num,st[105],top,color[105],rd[105];
struct node{
    int y,next;
}b[10005];
void add(int s,int t){
    b[++tot].y=t;
    b[tot].next=head[s];
    head[s]=tot;
}
void dfs(int x){
    for (int k=head[x];k;k=b[k].next){
        int y=color[b[k].y];
        if (!vis[y]){
            vis[y]=1;
            dfs(y);
            for (int i=m;i>=0;--i)
                for (int j=m-i;j>=0;--j){
                    f[x][i+j]=max(f[x][i+j],f[y][j]+f[x][i]);
                }
        }
    }
}
void tarjan(int x){
    dfn[x]=low[x]=++dfs_num;
    st[++top]=x;
    vis[x]=1;
    for (int k=head[x];k;k=b[k].next){
        int y=b[k].y;
        if (!dfn[y]){
            tarjan(y);
            cmin(low[x],low[y]);
        }
        else if (vis[y]) cmin(low[x],low[y]);
    }
    if (dfn[x]==low[x]){
        vis[x]=0;
        color[x]=x;
        int y;
        while (y=st[top],y!=x){
            color[y]=x;
            w[x]+=w[y];
            v[x]+=v[y];
            vis[y]=0;
            top--;
        }   
        top--;
    }
}
int main()  
{  
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    memset(f,-0x3f,sizeof(f));
    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>>k;
        if (k!=0) add(k,i);
    }
    for (int i=1;i<=n;++i)
        if (!dfn[i]) tarjan(i);
    for (int i=1;i<=n;++i){
        for (int k=head[i];k;k=b[k].next)
            if (color[i]!=color[b[k].y]){
                ++rd[color[b[k].y]];
                if (i!=color[i]) add(color[i],color[b[k].y]);
            }
    }
    for (int i=1;i<=n;++i)
        if (i==color[i] && !rd[i]) add(0,i);
    for (int i=0;i<=n;++i)
        if (color[i]==i) f[i][w[i]]=v[i];
    memset(vis,0,sizeof(vis));
    dfs(0);
    ans=0;
    for (int i=0;i<=m;++i)
        ans=max(ans,f[0][i]);
    cout<<ans<<endl;
}

对拍都拍不出错,交上去就wa5,6两个点

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



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