[数据结构与算法]6.18训练日记

每天起床第一句,先给自己打个气。
今天的我也要好好训练
鸽了好久的训练,沉迷了两天游戏,及时醒悟过来

本想下一个英雄联盟晚上休息的时候玩玩,看来是没有这个福分了.

P2515 [HAOI2010]软件安装

链接
思路:很快发现,对于一个SCC来说,里面的点要么选,要么都不选,因为只选其中的一些点,是不能满足题目中的前置条件都满足的.
再观察,这个图很特殊,最多有n条边,而且每个点的入度最多只有1,因为每个软件只依赖于另外一个软件.,我们很快发现,SCC出现后,SCC内的每个点入度至少是1,而原图又要求每个点入度至多为1,意味着SCC内与其他的点一定是割离开来的.
既然这样,把SCC缩成一个点后,连向树根.而且我们发现了,如果至少有一个$D_i=0$,那么就会有一个树根,如果没有,就需要建立一个虚的树根去连接.
建模完毕,用$dp(i,j)$表示,考虑以$i$为根,若使用了$j$个磁盘空间所能获得最大的价值是多少.
不难发现,是一个树上背包的模型,因为每个结点的状态是一个数组.对于每个节点,需要得到一个数组$dp(j)$,代表给这个点$j$个空间得到最大利润是多少.
而物品的描述又是:$dp(v,k)$,给$k个空间,物品v能带来的最大利润为dp(v,k)$
不要忘了,每个物品只能用一次,转移方程不想写了,就看代码吧(反正也没人看)
反正这题就是缩点后的树上背包,背包类型是n件物品选一个,需要枚举空间再枚举物品,因为物品只能选一个.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 505;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int dfn[maxn],dfs_clock=0;int low[maxn];int sccnow[maxn];
stack<int>S;int scc_cnt = 0;
vector<int> G[maxn];
int scc_v[maxn];int scc_w[maxn];
int W[maxn],V[maxn];
void Tarjan(int u){
	dfn[u]=low[u]=++dfs_clock;
	S.push(u);
	for(auto v : G[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(!sccnow[v]) low[u] =min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		scc_cnt++;
		while(true){
			int x = S.top();S.pop();
			scc_w[scc_cnt] +=W[x];
			scc_v[scc_cnt] +=V[x];
			sccnow[x] = scc_cnt;
			if(x==u) break;
		}
	}
}
void find_scc(int n){
	dfs_clock = 0;
	for(int i=1;i<=n;i++) {
		if(!dfn[i]) Tarjan(i);
	}
}
vector<int> G1[maxn];
vector<pii> edge;
set<pii> mp;
int in[maxn];//in_deg in new graph
void make_graph(){
	for(auto [u,v] : edge){
		if(sccnow[u]!=sccnow[v]&&!mp.count({sccnow[u],sccnow[v]})){
			mp.insert({sccnow[u],sccnow[v]});
			G1[sccnow[u]].push_back(sccnow[v]);
			in[sccnow[v]]++;
		}
	}
	for(int i=1;i<=scc_cnt;i++){
		if(in[i]==0) G1[0].push_back(i);//void point
	}
}
//dp use new graph G1,scc_w,scc_v
int dp[maxn][maxn];int m;
void dfs(int u){
	for(int i=scc_w[u];i<=m;i++) dp[u][i] = scc_v[u];
	for(auto v : G1[u]){
		dfs(v);
		for(int j=m;j>=scc_w[u];j--){
			for(int i=0;i<=j;i++){
				dp[u][j] = max(dp[u][j],dp[u][j-i]+dp[v][i]);
			}
		}
	}
}
signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	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++){
		int D;cin>>D;
		if(D==0) continue;
		G[D].push_back(i);
		edge.push_back({D,i});
	}
	for(int i=0;i<=500;i++){
		for(int j=0;j<=500;j++) dp[i][j] = -INF;
	}
	//input
	find_scc(n);
	make_graph();
	dfs(0);
	cout<<max(0LL,dp[0][m])<<"\n";
return 0;}