BZOJ2427: [HAOI2010]软件安装 tarjan+树形背包

分析:

一开始我以为是裸的树形背包...之后被告知这东西...可能有环...什么!有环!

有环就搞掉就就可以了...tarjan缩点...建图记得建立从i到d[i]之后跑tarjan,因为这样才能判断出环的情况...

缩点之后重新建图就需要见d[i]到i了...

附上代码:

#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
#define N 205
struct node
{
int to,next;
}e[N];
int f[N][505],head[N],cnt,dfn[N],low[N],vis[N],sta[N],top,tims,fa[N],n,m,a[N],b[N],in1[N];
void add(int x,int y){if(!y)return;e[cnt]=(node){y,head[x]};head[x]=cnt++;}
void tarjan(int x)
{
dfn[x]=low[x]=++tims;sta[++top]=x;vis[x]=1;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
if(vis[to1])low[x]=min(dfn[to1],low[x]);
else if(!dfn[to1])tarjan(to1),low[x]=min(low[x],low[to1]);
}
if(dfn[x]==low[x])
{
while(sta[top]!=x)
{
fa[sta[top]]=x;
vis[sta[top]]=0;
top--;
}
fa[x]=x;vis[x]=0;top--;
}
}
vector <int>v[N];
void dfs(int x)
{
for(int i=0;i<v[x].size();i++)
{
int to1=v[x][i];
dfs(to1);
for(int j=m;j;j--)
{
for(int k=j;~k;k--)
{
f[x][j]=max(f[to1][k]+f[x][j-k],f[x][j]);
}
}
}
for(int i=m;i>=b[x];i--)f[x][i]=f[x][i-b[x]]+a[x];
for(int i=0;i<b[x];i++)f[x][i]=0;
}
int main()
{
scanf("%d%d",&n,&m);memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1,x;i<=n;i++)scanf("%d",&x),add(i,x);
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
{
for(int j=head[i];j!=-1;j=e[j].next)
{
int to1=e[j].to;
if(fa[to1]!=fa[i])v[fa[to1]].push_back(fa[i]),in1[fa[i]]++;
}
}
for(int i=1;i<=n;i++)if(fa[i]==i&&(!in1[i]))v[0].push_back(i);
for(int i=1;i<=n;i++)if(fa[i]!=i)a[fa[i]]+=a[i];
for(int i=1;i<=n;i++)if(fa[i]!=i)b[fa[i]]+=b[i];
dfs(0);printf("%d\n",f[0][m]);return 0;
}

  

上一篇:scp出现Permission denied,please try again的解决办法


下一篇:Android APP压力测试实战