游客 注册 | 登录
中文 | En

3773 - 软件安装

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

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

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

题目输入

第1行：N，M (0<=N<=100．0<=M<=500)

第2行：W1，W2，…，Wi，…，Wn(0<=Wi<=M)

第3行：V1，V2，…，Vi，…，Vn(0<=Vi<=1000)

第4行：D1，D2，…，Di，…，Dn(0<=Di<=N，Di≠i)

题目输出

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

 

输入/输出样例

输入格式

3 10
5 5 6
2 3 4
0 1 1

输出格式

5

C++解答

#define MAX(A,B) ((A)>(B)?(A):(B))
#define MIN(A,B) ((A)<(B)?(A):(B))
#define MAXN 110
#include<cstdio>
#include<cstring>

using namespace std;

int n, m, t, num, head, cnt, dnf[MAXN], low[MAXN], d[MAXN], w[MAXN], v[MAXN], ru[MAXN], sta[MAXN], bg[MAXN], wt[MAXN], my[MAXN], ch[MAXN][2], f[MAXN][510];
bool ins[MAXN], vis[MAXN];

struct me {
	int qian, hou, nt;
}sg[MAXN];

void ADD(int x,int y) {
	sg[++t].hou = y;
	sg[t].qian = x;
	sg[t].nt = d[x];
	d[x] = t;
}
void TARJAN(int x) {
	vis[x] = true;
	low[x] = dnf[x] = ++num;
	sta[++head] = x;
	ins[x] = true;
	for(int i = d[x] ; i != -1 ; i = sg[i].nt) {
		if(!vis[sg[i].hou]) {
			TARJAN(sg[i].hou);
			low[x] = MIN(low[x], low[sg[i].hou]);
		} else {
			if(ins[sg[i].hou]) {
				low[x] = MIN(low[x], dnf[sg[i].hou]);
			}
		}
	}
	if(low[x] == dnf[x]) {
		int op;
		++cnt;
		do {
			op = sta[head--];
			//printf("%d belong to -> %d\n", op, cnt);
			ins[op] = false;
			bg[op] = cnt;
		} while(op!=x);
	}
	return;
}

void DP(int x,int k) {
	if(!x&&k) {
		return;
	}
	DP(ch[x][1], k+1);
	DP(ch[x][0], k+1);
	if(m>wt[x]) {
		for(int i = 1 ; i < wt[x] ; ++ i) {
			f[x][i] = f[ch[x][1]][i];
		}
		f[x][wt[x]] = MAX(my[x], f[ch[x][1]][wt[x]]);
		for(int i = wt[x]+1 ; i <= m ; ++ i) {
			f[x][i] = MAX(f[x][i-1], f[ch[x][1]][i]);
			for(int j = 0 ; j <= i-wt[x] ; ++ j) {
				f[x][i] = MAX(f[x][i], f[ch[x][0]][j]+f[ch[x][1]][i-wt[x]-j]+my[x]);
			}
		//	printf("f[%d][%d] = %d\n", x, i, f[x][i]);
		}
	} else {
		for(int i = 1 ; i <= m ; ++ i) {
			f[x][i] = f[ch[x][1]][i];
		}
		if(m==wt[x]) {
			f[x][m] = MAX(f[x][m], my[x]);
		}
	}
}

int main() {
	int x;
	memset(d, -1, sizeof(d));
	scanf("%d%d", &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", &x);
		if(x) {
			ADD( x, i);
		}
	}
	for(int i = 1 ; i <= n ; ++ i) {
		if(!vis[i]) {
			TARJAN(i);
		}
	}
	for(int i = 1 ; i <= n ; ++ i) {
		my[bg[i]] += v[i];
		wt[bg[i]] += w[i];
	}
	int nu = 0;
	for(int i = 1 ; i <= t ; ++ i) {
		if(bg[sg[i].qian]!=bg[sg[i].hou]) {
		    ++nu;
			++ru[bg[sg[i].hou]];
			if(ch[bg[sg[i].qian]][0]) {
				int q = ch[bg[sg[i].qian]][0], p;
				while(q) {
					p = q;
					q = ch[q][1];
				}
				ch[p][1] = bg[sg[i].hou];
			} else {
				ch[bg[sg[i].qian]][0] = bg[sg[i].hou];
			}
		}
	}
	for(int i = 1 ; i <= cnt ; ++ i) {
		if(!ru[i]) {
			++nu;
			if(!ch[0][0]) {
				ch[0][0] = i;
			} else {
				int q= ch[0][0], p;
				while(q) {
					p = q;;
					q = ch[q][1];
				}
				ch[p][1] = i;
			}
		}
	}
	DP(0,0);
	printf("%d", f[ch[0][0]][m]);
	getchar();
	getchar();
	return 0;
}
请先登陆