P2515 [HAOI2010] 软件安装

~~~~~      P2515 [HAOI2010] 软件安装 ~~~~~      总题单链接

思路

~~~~~      发现构成的图是一个森林和一些环。

~~~~~      对于森林，建一个虚点然后树形 $DP$ 即可。

~~~~~      对于环，发现要么把这个环上的每一个点都选了，要么每一个都不选。所以可以先缩点。

~~~~~      缩点后跑树形 $dp$ 就行了。

代码

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;ll n,m,v[505],w[505];
ll dfn[505],low[505],tot;
ll scc[505],din[505],cnt;
ll stk[505],ins[505],top;
vector<ll>eg[505],ng[505];
ll scw[505],scv[505],dp[505][505];void Tarjan(ll p){dfn[p]=low[p]=++tot;stk[++top]=p;ins[p]=1;for(ll v:eg[p]){if(!dfn[v]){Tarjan(v);low[p]=min(low[p],low[v]);}else if(ins[v])low[p]=min(low[p],dfn[v]);}if(low[p]==dfn[p]){cnt++;while(1){ll z=stk[top--];ins[z]=0;scc[z]=cnt;scv[cnt]+=v[z];scw[cnt]+=w[z];if(z==p)break;}}
}void dfs_dp(ll p){if(scv[p]<=m)dp[p][scv[p]]=scw[p];for(ll v:ng[p]){dfs_dp(v);for(ll i=m;i>=scv[p];i--)for(ll j=m;j>=0;j--)if(i+j<=m)dp[p][i+j]=max(dp[p][i+j],dp[p][i]+dp[v][j]);}
}signed main(){ios::sync_with_stdio(false);cin>>n>>m;for(ll i=1;i<=n;i++)cin>>v[i];for(ll i=1;i<=n;i++)cin>>w[i];for(ll i=1;i<=n;i++){ll f;cin>>f;eg[f].push_back(i);}for(ll i=1;i<=n;i++)if(!dfn[i])Tarjan(i);for(ll u=1;u<=n;u++)for(ll v:eg[u]){if(scc[u]==scc[v])continue;ng[scc[u]].push_back(scc[v]);din[scc[v]]++;}for(ll i=1;i<=cnt;i++)if(!din[i])ng[0].push_back(i);memset(dp,-0x3f,sizeof(dp));dfs_dp(0);ll ans=0;for(ll i=0;i<=m;i++)ans=max(ans,dp[scc[0]][i]);cout<<ans;return 0;
}