样例过了,但全wa,玄关求调
查看原帖
样例过了,但全wa,玄关求调
1632297
ymgh楼主2025/7/28 21:16
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int head[N],dfn[N],low[N];
int stk[N],ins[N],c[N];
int indegree[N];
int tot,num,top;
int edge_cnt,scc_cnt;
vector<int> scc[N];
int n,m;
struct node {
	int nxt,to;
}edge[105];
int vis[105];
int f[105][505];
void add(int from,int to){
	edge_cnt++;
	edge[edge_cnt].nxt=head[from];
	edge[edge_cnt].to=to;
	head[from]=edge_cnt;	
}
int w[105],w1[105];//内存; 
int v[105],v1[105];//价值; 
void tarjan(int x) {
    dfn[x]=low[x]=++num;
    stk[++top]=x,ins[x]=1;
    for (int i=head[x];i;i=edge[i].nxt) {
        int y=edge[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x]==low[x]) {
        scc_cnt++;
        int y;
        do {
            y=stk[top--];
            ins[y]=0;
            c[y]=scc_cnt;
            w1[scc_cnt]+=w[y];
            v1[scc_cnt]+=v[y];
            scc[scc_cnt].push_back(y);
        } while (x!=y);
    }
}
int tc;
int vc[N],nc[N],hc[N];
void add_c(int x,int y){
	vc[++tc]=y;
	nc[tc]=hc[x];
	hc[x]=tc;
}
void dfs(int u) {
    if (w1[u]<=m) {
        for(int i=w1[u];i<=m;i++) f[u][i]=v1[u];
    }
    for (int i=hc[u];i;i=nc[i]) {
        int v=vc[i];
        dfs(v);
        for (int j=m;j>=w1[u];j--) {
            for (int k=0;k<=j-w1[u];k++) {
                if (f[v][k]+f[u][j-k]>f[u][j]) {
                    f[u][j]=f[v][k]+f[u][j-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];
	}
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		if(x!=0){
			add(i,x);
		}
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].to;
		if(c[x]==c[y]) continue;
		add_c(c[x],c[y]);
		indegree[c[y]]++;
	  }
    }
    for(int i=1;i<=scc_cnt;i++){
    	if(indegree[i]==0){
    		add_c(0,i);
    	}
    }
    w1[0]=0;
    v1[0]=0;
    dfs(0);
    cout<<f[0][m]<<endl;
	return 0;
}
2025/7/28 21:16
加载中...