社区讨论

用拓扑序来dp为什么不对?

P2515[HAOI2010] 软件安装参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@m3zun8cl
此快照首次捕获于
2024/11/27 20:15
去年
此快照最后确认于
2025/11/04 13:48
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define llINF 0x3f3f3f3f3f3f3f3f
const int R=6e3+10;
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int dfn[R],low[R];
int stk[R];
vector<int>G[R],g[R];
set<int>vt[R];
int timestamp;
bool in_stk[R];
int top;
int id[R],sz[R];
int scc_cnt;
int n,m;
int w[R],v[R],fa[R],val[R],wal[R];
int in[R];
int f[102][70020];

void tarjan(int u){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u;
	in_stk[u]=true;
	
	for(int v:G[u]){
		if( !dfn[v] ){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		
		else if( in_stk[v] ){
			low[u]=min( low[u],dfn[v] );
		}
		
	}
	
	if( dfn[u] == low[u] ){
		++scc_cnt;
		int y;
		do{
			y=stk[top--];
			in_stk[y]=false;
			id[y]=scc_cnt;
			//vt[scc_cnt].is(y);
			sz[scc_cnt]++;
			wal[scc_cnt]+=w[y];
			val[scc_cnt]+=v[y];
			//f[scc_cnt][1]=val[scc_cnt];
		}while(y!=u);
		
	}
	
}


void solve(){
    
    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>>fa[i];if(fa[i]!=0)G[fa[i]].pb(i);}
    
    for(int i=1;i<=n;i++){
    	if(!dfn[i])tarjan(i); 
    }

    
    for(int i=1;i<=n;i++){
    	int j1=id[i];
    	for(int v:G[i]){
    		int j2=id[v];
    		if( j1!=j2 )g[j1].pb(j2),in[j2]++;
    	}
    }
    
    int ans=0;
    queue<int>q;
    for(int i=0;i<=101;i++){
    	for(int j=0;j<=50000;j++)f[i][j]=-llINF;
    }
    for(int i=1;i<=scc_cnt;i++){
    	if( in[i]==0 ){
    		q.push(i); 
    		for(int j=wal[i];j<=m;j++)f[i][j]=val[i],ans=max(ans,val[i]);
    	}    	
    }

    
    while(q.size()){
    	//cout<<
    	int u=q.front();q.pop();
    	for(int v:g[u]){
    		for(int j=0;j<=m;j++){ 
    			if( j>=wal[v] && f[u][j-wal[v] ]>=0 ) f[v][j]=max( f[v][j] , f[u][j-wal[v]] + val[v] );
				ans=max(ans,f[v][j]);  
    		}
    		
    		in[v]--;
    		if( in[v]==0 )q.push(v);
    	}
    }
    
    cout<<ans<<endl;

}
 

signed main()
{
   IOS; 
   int T;T=1;
   while(T--) solve();
}

这个问题缩点后一定要用树形dp吗,用拓扑序来dp为什么不对。感谢大家帮助。

回复

3 条回复,欢迎继续交流。

正在加载回复...