【Luogu】P2515软件安装(树形DP)
2024-08-24 06:20:35
这么水的题我一遍没A,而且前两次提交都只有十分。气死我了。本来我的博客拒收水题来着。
Tarjan缩点之后跑树形DP即可。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define maxn 300
#define maxm 600
using namespace std; inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} int w[maxn];
int c[maxn];
int dfn[maxn],ID;
int low[maxn];
int stack[maxn],top;
int col[maxn],cnt;
int colw[maxn],colc[maxn];
bool vis[maxn];
int f[maxn][maxm];
int indl[maxn];
int n,m; struct Pic{
struct Edge{
int next,to;
}edge[maxn*];
int head[maxn],num;
Pic(){num=;memset(head,,sizeof(head)); }
inline void add(int from,int to){
edge[++num]=(Edge){head[from],to};
head[from]=num;
}
void tarjan(int x){
vis[x]=;stack[++top]=x;
dfn[x]=low[x]=++ID;
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to;
if(!dfn[to]){
tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(vis[to]) low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x]){
col[x]=++cnt;
vis[x]=; colw[cnt]=w[x]; colc[cnt]=c[x];
while(stack[top]!=x){
vis[stack[top]]=; col[stack[top]]=cnt;
colw[cnt]+=w[stack[top]]; colc[cnt]+=c[stack[top]];
top--;
}
top--;
}
}
void dfs(int x){
for(int i=m;i>=colw[x];--i) f[x][i]=colc[x];
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to;
dfs(to);
for(int j=m;j>=;--j)
for(int k=;j-k>=colw[x];++k) f[x][j]=max(f[x][j],f[x][j-k]+f[to][k]);
}
return;
}
}Old,New; int main(){
n=read();m=read();
for(int i=;i<=n;++i) w[i]=read();
for(int i=;i<=n;++i) c[i]=read();
for(int i=;i<=n;++i){
int x=read();
if(x) Old.add(x,i);
}
for(int i=;i<=n;++i)
if(!dfn[i]) Old.tarjan(i);
for(int i=;i<=n;++i)
for(int j=Old.head[i];j;j=Old.edge[j].next){
int to=Old.edge[j].to;
if(col[i]==col[to]) continue;
New.add(col[i],col[to]);
indl[col[to]]++;
}
for(int i=;i<=cnt;++i)
if(!indl[i]) New.add(,i);
New.dfs();
printf("%d",f[][m]);
return ;
}
最新文章
- 拼图小游戏之计算后样式与CSS动画的冲突
- ORACLE中常见SET指令
- 《HelloGitHub月刊》第07期
- 机器学习之分类器性能指标之ROC曲线、AUC值
- AngularJS中的指令
- 三、spinner
- vs2013的asp.net 管理
- linux C 9*9
- Loading Data into HDFS
- 传微软欲收购Xamarin:未来有望通过VS开发iOS和Android应用?
- Linux 的启动流程-阮一峰
- 请注意写代码的习惯与态度(Java)
- 重新安装了环境报错{";error";:";could not find driver";}
- 神经网络参数与TensorFlow变量
- js实现往数组中添加非存在的对象,如果存在就改变键值。
- 数据库隔离级别深入理解(ORACLE)
- [Python]Python 使用 for 循环的小例子
- (笔记)Linux内核学习(一)之内核介绍
- foreach嵌套遍历循环的问题
- Postgres 主从复制搭建步骤