社区讨论
用拓扑序来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 条回复,欢迎继续交流。
正在加载回复...