社区讨论

样例过了但是WA

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@m41f2okt
此快照首次捕获于
2024/11/28 22:35
去年
此快照最后确认于
2024/11/29 06:53
去年
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,dfn[110],low[110],cnt,belong[110],indeg[110];
ll W[110],V[110],ww[110],vv[110],dp[110][510];
vector<int> g[110];
stack<int> s;
vector<int> g2[110];
void tarjan(int u,int fa) {
	dfn[u] = low[u] = ++cnt;
	s.push(u);
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i];
		if (!dfn[v]) {
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
		} else if (!belong[v]) low[u] = min(low[u],dfn[v]);
	}
	if (low[u] == dfn[u]) {
		while (s.top() != u) {
			belong[s.top()] = u;
			ww[u] += W[s.top()];
			vv[u] += V[s.top()];
			s.pop();
		}
		belong[s.top()] = u;
		ww[u] += W[s.top()];
		vv[u] += V[s.top()];
		s.pop();
	}
	return;
}
bool find(int u,int v) {
	for (int i = 0;i < g2[u].size();i ++)
		if (g2[u][i] == v) return true;
	return false;
}
void build_g2() {
	for (int i = 1;i <= n;i ++)
		for (int j = 0;j < g[i].size();j ++) {
			int v = g[i][j];
			if (belong[i] != belong[v]) {
				if (find(belong[i],belong[v])) continue;////////////
				g2[belong[i]].push_back(belong[v]);
				++ indeg[belong[v]];
			}
		}
	
	//!!!!!!!!!!
	for (int i = 1;i <= n;i ++)
		if (belong[i] == i && !indeg[i]) g2[0].push_back(i);
	//!!!!!!!!!!
	
	return;
}
void dfs(int u,int fa) {
	for (int i = 0;i <= m;i ++)
		if (i >= ww[u]) dp[u][i] = vv[u];
		else dp[u][i] = LONG_LONG_MIN;
	for (int i = 0;i < g2[u].size();i ++) {
		int v = g2[u][i];
		if (v != fa) {
			dfs(v,u);
			for (int i = m;i >= ww[u];i --)
				for (int j = ww[u];j <= i;j ++)
					dp[u][i] = max(dp[u][i],dp[u][i - j] + dp[v][j]);
		}
	}
	return;
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= n;i ++)
		scanf("%lld",&W[i]);
	for (int i = 1;i <= n;i ++)
		scanf("%lld",&V[i]);
	for (int i = 1;i <= n;i ++) {
		ll d;
		scanf("%lld",&d);
		if (d) g[i].push_back(d);
	}
	for (int i = 1;i <= n;i ++)
		if (!dfn[i]) tarjan(i,0);
	build_g2();
	dfs(0,0);
	printf("%lld\n",dp[0][m]);
	return 0;
}

回复

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

正在加载回复...