题目链接

  这么水的题我一遍没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 ;
}

最新文章

  1. 拼图小游戏之计算后样式与CSS动画的冲突
  2. ORACLE中常见SET指令
  3. 《HelloGitHub月刊》第07期
  4. 机器学习之分类器性能指标之ROC曲线、AUC值
  5. AngularJS中的指令
  6. 三、spinner
  7. vs2013的asp.net 管理
  8. linux C 9*9
  9. Loading Data into HDFS
  10. 传微软欲收购Xamarin:未来有望通过VS开发iOS和Android应用?
  11. Linux 的启动流程-阮一峰
  12. 请注意写代码的习惯与态度(Java)
  13. 重新安装了环境报错{&quot;error&quot;:&quot;could not find driver&quot;}
  14. 神经网络参数与TensorFlow变量
  15. js实现往数组中添加非存在的对象,如果存在就改变键值。
  16. 数据库隔离级别深入理解(ORACLE)
  17. [Python]Python 使用 for 循环的小例子
  18. (笔记)Linux内核学习(一)之内核介绍
  19. foreach嵌套遍历循环的问题
  20. Postgres 主从复制搭建步骤

热门文章

  1. ActiveX、OLE和COM/DCOM
  2. setup命令
  3. python爬虫之路——初识爬虫三大库,requests,lxml,beautiful.
  4. Windows UEFI 安装策略的一个细节
  5. [VC]listctrl的基本用法
  6. C#textbox允许换行
  7. 为DataGridView控件实现复选功能
  8. python_96_类的继承1
  9. Ajax的原理及Django上传组件
  10. laydate时间控件绑定回调事件