求助~不知道哪里错了的蒟蒻
查看原帖
求助~不知道哪里错了的蒟蒻
678858
ShiRoZeTsuHL卜奎BBQ!楼主2022/10/12 08:03
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 105;
const int maxm = 505;
#define _SCH(u) for(int _ = HEAD[u], v = E[_].to; _; _ = E[_].nxt, v = E[_].to)
#define _sch(u) for(int _ = head[u], v = e[_].to; _; _ = e[_].nxt, v = e[_].to)

int n, m, dfncnt, top, scccnt;
int we[maxn], ve[maxn], scc[maxn];
int dfn[maxn], low[maxn], stk[maxn];
int f[maxn][maxm], in[maxn];
bool vis[maxn];

struct edge {
	int from, to, nxt;
} e[maxn<<1], E[maxn];
int tot, TOT, head[maxn], HEAD[maxn];
void ADD(int u, int v) {
	E[++TOT].to = v;
	E[TOT].from = u;
	E[TOT].nxt = HEAD[u];
	HEAD[u] = TOT;
}
void add(int u, int v) {
	e[++tot].to = v;
	e[tot].nxt = head[u];
	head[u] = tot;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++dfncnt;
	vis[u] = true;
	stk[++top] = u;
	_SCH(u) {
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(vis[v])
			low[u] = min(low[u], low[v]);
	}
	if(dfn[u] == low[u]) {
		int v;
		scccnt++;
		while((v = stk[top--])) {
			scc[v] = u;
			vis[v] = false;
			if(u == v) break;
			we[u] += we[v];
			ve[u] += ve[v];
		} 
	}
}

void dfs(int u) {
	for(int i = m; i >= we[u]; i--)
		f[u][i] = ve[u];
	_sch(u) {
		dfs(v);
		for(int i = m; i >= 0; i--)
		for(int k = 0; k <= i; k++)
			f[u][i] = max(f[u][i], f[u][i-k] + f[v][k]);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &we[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &ve[i]);
	for(int i = 1, from; i <= n; i++) {
		scanf("%d", &from);
		if(from) ADD(from, i);
	}
	for(int i = 1; i <= n; i++)
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= TOT; i++) {
		int u = scc[E[i].from], v = scc[E[i].to];
		if(u != v) add(u, v), in[v]++;
	}
	for(int i = 1; i <= scccnt; i++)
		if(!in[i]) add(0, i);
	dfs(0);
	printf("%d\n", f[0][m]);
	return 0;
}
2022/10/12 08:03
加载中...