[BZOJ]2427: [HAOI2010]软件安装

　　题解: 树上背包合并裸题需要考虑有环所以缩环成一个点这点的价值等于环上所有点的价值和

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=105;
const int NM=505;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int f[MAXN];
int n,m;
int w[MAXN],v[MAXN];
typedef struct node{
    int x,y;
}node;
node d[MAXN];
vector<int>vec[MAXN];
bool vis[MAXN],c[MAXN];
int st[MAXN],tot,cnt;
vector<int>circle[MAXN];
void tarjan(int x,int y){
    cnt++;
    dec(i,tot,1){
	if(st[i]==y)break;
	circle[cnt].pb(st[i]);
    }
    circle[cnt].pb(y);
}


void dfs(int x){
    vis[x]=1;st[++tot]=x;c[x]=1;
    for(int i=0;i<vec[x].size();i++){
	int t=vec[x][i];
	if(c[t])tarjan(x,t);
	else if(!vis[t])dfs(t);
    }
    tot--;c[x]=0;
}

int find1(int x){
    if(x==f[x])return x;
    return f[x]=find1(f[x]);
}

int dp[MAXN][NM];

void _dfs(int x){
    if(w[x]<=m)dp[x][w[x]]=v[x];
    link(x){
	_dfs(j->t);
	for(int i=m;i>=w[x]+w[j->t];i--)for(int k=w[j->t];k<=i-w[x];k++)dp[x][i]=max(dp[x][i],dp[j->t][k]+dp[x][i-k]);
    }
}


int ci[MAXN];

int main(){
    n=read();m=read();
    inc(i,1,n)f[i]=i;
    inc(i,1,n)w[i]=read();
    inc(i,1,n)v[i]=read();
    int tot1=0;
    inc(i,1,n){
	int t=read();
	if(t==0){continue;}
	vec[t].pb(i);
	++tot1;
	d[tot1].x=t;d[tot1].y=i;
    }
    inc(i,1,n)if(!vis[i])dfs(i);
    inc(i,1,cnt){
	for(int j=1;j<circle[i].size();j++){
	    int t1=find1(circle[i][j]);int t2=find1(circle[i][j-1]);
	    if(t1==t2)continue;
	    f[t1]=t2;w[t2]+=w[t1];v[t2]+=v[t1];
	}
    }
    inc(i,1,tot1){
	int t1=find1(d[i].x);int t2=find1(d[i].y);
	if(t1==t2)continue;
	add(t1,t2);ci[t2]++;
    }
    inc(i,1,n){
	int t1=find1(i);
	if(t1==i&&!ci[i])add(0,i);
    }
    _dfs(0);
    int ans=0;
    inc(i,1,m)ans=max(ans,dp[0][i]);
    printf("%d
",ans);
}

2427: [HAOI2010]软件安装

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2519 Solved: 1090
[Submit][Status][Discuss]

Description

现在我们的手头有N个软件，对于一个软件i，它要占用W_i的磁盘空间，它的价值为V_i。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即V_i的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件D_i。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则D_i=0，这时只要这个软件安装了，它就能正常工作。

Input

第1行：N, M  （0<=N<=100, 0<=M<=500）
      第2行：W₁, W₂, ... W_i, ..., W_n （0<=W_i<=M ）
      第3行：V₁, V₂, ..., V_i, ..., V_n  （0<=Vi<=1000 ）
      第4行：D₁, D₂, ..., D_i, ..., D_n（0<=D_i<=N, D_i≠i ）

Output

一个整数，代表最大价值。

Sample Input

3 10
5 5 6
2 3 4
0 1 1