社区讨论
样例过了但是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 条回复,欢迎继续交流。
正在加载回复...