榆林公司做网站外链发布

[HAOI2010]软件安装

开始没有看懂题，以为就是个树形依赖背包，打完之后W40，然后才发现它会有还，要用tarjan缩完点后跑背包，要建立一个虚拟节点0连接所有的子图（注意连接的位置）。

但是有个细节卡了我好长时间：

错误示范：

for(int i=1;i<=n;i++)//这样会导致0连接的不是入度为0的点（或环）
    if(!Dsn[i])
    {
        tarjan(i);
        add(0,i);
    }

正确代码：

    for(int i=1;i<=tot;i++)
    if(!du[i])
        add2(0,i);

在缩点是记录每个scc的入度，0直接和入度为0的scc连接。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define MAXN 110
#define ma(x) memset(x,0,sizeof(x))
using namespace std;
struct edge
{int u,v,nxt;#define u(x) ed[x].u#define v(x) ed[x].v#define n(x) ed[x].nxt#define u2(x) ed2[x].u#define v2(x) ed2[x].v#define n2(x) ed2[x].nxt
}ed[5010],ed2[5010];
int first[MAXN],num_e;
#define f(x) first[x]
int first2[MAXN],num_e2;
#define f2(x) first2[x]
int n,m;
int w[MAXN],v[MAXN],d[MAXN];
int w2[MAXN],v2[MAXN];int Dsn[MAXN],Low[MAXN],cnt;
int stack[MAXN],top;
bool vi[MAXN];
int belong[MAXN],tot;
int du[MAXN];
vector<int> scc[MAXN];
void tarjan(int x)
{Dsn[x]=++cnt;Low[x]=cnt;stack[++top]=x;vi[x]=1;for(int i=f(x);i;i=n(i))if(!Dsn[v(i)])tarjan(v(i)),Low[x]=min(Low[x],Low[v(i)]);else if(vi[v(i)])Low[x]=min(Low[x],Low[v(i)]);if(Dsn[x]==Low[x])	{++tot;vi[x]=0;while(stack[top]!=x){vi[stack[top]]=0;scc[tot].push_back(stack[top]);belong[stack[top--]]=tot;}scc[tot].push_back(stack[top]);belong[stack[top--]]=tot;}
}
inline void add(int u,int v)
{++num_e;u(num_e)=u;v(num_e)=v;n(num_e)=f(u);f(u)=num_e;
}
inline void add2(int u,int v)
{++num_e2;u2(num_e2)=u;v2(num_e2)=v;n2(num_e2)=f2(u);f2(u)=num_e2;
}
int f[MAXN][510];
void dfs(int x)
{f[x][w2[x]]=v2[x];for(int i=f2(x);i;i=n2(i)){dfs(v2(i));for(int j=m;j>=w2[x];j--)for(int k=0;k<=m;k++){if(j+k>m)break;f[x][j+k]=max(f[x][j+k],f[x][j]+f[v2(i)][k]);	}}
}
signed main()
{
//	freopen("in.txt","r",stdin);cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&w[i]);for(int i=1;i<=n;i++)scanf("%d",&v[i]);for(int i=1;i<=n;i++){scanf("%d",&d[i]);if(d[i])add(d[i],i);}for(int i=1;i<=n;i++)if(!Dsn[i])tarjan(i);for(int i=1;i<=num_e;i++)if(belong[u(i)]!=belong[v(i)]){add2(belong[u(i)],belong[v(i)]);	du[belong[v(i)]]++;}for(int i=1;i<=tot;i++)if(!du[i])add2(0,i);for(int i=1;i<=tot;i++){for(int j=0;j<scc[i].size();j++){w2[i]+=w[scc[i][j]];v2[i]+=v[scc[i][j]];}}dfs(0);int ans=0;for(int i=1;i<=m;i++)ans=max(ans,f[belong[0]][i]);printf("%d\n",ans);
}