记录编号	240220	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-03-22 11:59:22	内存使用	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];
inline int get_num() {
	char tmp;
	int ans = 0;
	tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp <= '9' && tmp >= '0') {
		ans = ans*10 + tmp-'0';
		tmp = getchar();
	}
	return ans;
} 
struct edge {
	int to, ne;
	edge() {}
	edge(int to_, int ne_) { to = to_, ne = ne_; }
}e[maxn];
int head[maxn], tot;
inline void add_edge(int fr, int to) {
	e[++tot] = edge(to, head[fr]); head[fr] = tot;
}
inline 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;
		}
	}
} 
inline void read() {
	n = get_num(); m = get_num();
	for(int i = 1; i <= n; i++) {
		w[i] = get_num();
	}
	for(int i = 1; i <= n; i++) {
		v[i] = get_num();
	}
	for(int i = 1; i <= n; i++) {
		need[i] = get_num();
	}
}
inline void dp(int now, int le) {
	if(le <= 0) return;
	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];
		if(le-w[to] <= 0) continue;
		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]);
	}
}
inline 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;
}