记录编号	240213	评测结果	AAAAAAAAAA
题目名称	444.[HAOI 2010]软件安装	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-03-22 11:15:50	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 200;
int stack[maxn], top;
bool vis[maxn];
bool instack[maxn];
int ref[maxn], cnt;
int v[maxn], w[maxn], need[maxn];
int n, m;
int f[maxn][maxn*5];
struct edge {
	int to, ne;
	edge() {}
	edge(int to_, int ne_) { to = to_, ne = ne_; }
}e[maxn];
int head[maxn], tot;
void add_edge(int fr, int to) {
	e[++tot] = edge(to, head[fr]); head[fr] = tot;
}
void get_node() {
	for(int i = 1; i <= n; i++) {
		ref[i] = i;
	}
	cnt = n;
	int now, tmp;
	for(int i = 1; i <= n; i++) {
		if(vis[i]) continue;
		now = i;
		bool is_loop = false;
		do {
			if(vis[now]) {
				if(instack[now]) is_loop = true;
				break;
			}
			vis[now] = instack[now] = true;
			stack[++top] = now;
			now = need[now];
		} while (true);
		if(is_loop) {
			cnt++;
			do {
				tmp = stack[top--];
				instack[tmp] = false;
				ref[tmp] = cnt;
				w[cnt] += w[tmp];
				v[cnt] += v[tmp];
				if(tmp == now) break;
			} while(top);
		}
		while(top) {
			tmp = stack[top--];
			instack[tmp] = false;
		}
	}
} 
void read() {
	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", &need[i]);
	}
}
void dp(int now, int le) {
	for(int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		for(int j = 0; j <= le; j++) f[to][j] = f[now][j];
		dp(to, le-w[to]);
		for(int j = w[to]; j <= le; j++) f[now][j] = max(f[now][j], f[to][j-w[to]]+v[to]);
	}
}
void solve() {
	get_node();
	for(int i = 1; i <= n; i++) {
		if(ref[i] == ref[need[i]]) continue;
		add_edge(ref[need[i]], ref[i]);
	}
	for(int i = n+1; i <= cnt; i++) {
		add_edge(0, i);
	}
	dp(0, m);
	printf("%d", f[0][m]);
}
int main() {
	freopen("install.in", "r", stdin);
	freopen("install.out", "w", stdout);
	read();
	solve();
	return 0;
}