10pts 只 A 了 #2 求调
查看原帖
10pts 只 A 了 #2 求调
548203
KK_lang楼主2023/8/4 21:00

rt

#include<bits/stdc++.h>
using namespace std;

const int nr = 1e4 + 10;
const int mr = 1e5 + 10;
int n, m, tw[110], tv[110], w[110], v[110], t, ans, cnum;
int dfn[110], low[110], col[110], f[110][510];
struct Edge { int u, v; } e[110];
vector<int> adj[110], adn[110];
stack<int> st;

void solve(int x)
{
    st.pop();
    col[x] = cnum;
    w[col[x]] += tw[x];
    v[col[x]] += tv[x];
}

void Tarjan(int x)
{
    dfn[x] = low[x] = ++t;
    st.push(x);
    for (int i = 0; i < adj[x].size(); i++)
        if (dfn[adj[x][i]] == 0) 
        {
            Tarjan(adj[x][i]);
            low[x] = min(low[x], low[adj[x][i]]);
        }
        else if (col[adj[x][i]] == 0) low[x] = min(low[x], dfn[adj[x][i]]);
    if (low[x] == dfn[x])
    {
        cnum++;
        while (st.top() != x) solve(st.top());
        solve(x);
    }
}

void dfs(int x)
{
	for (int i = 0; i < adn[x].size(); i++)
	{
		dfs(adn[x][i]);
		for (int j = m; j >= w[x]; j--)
			for (int k = j; k >= w[x]; k--)
				f[x][j] = max(f[x][j], f[x][k] + f[adn[x][i]][j - k]);
	}
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> tw[i];
    for (int i = 1; i <= n; i++) cin >> tv[i];
    for (int i = 1; i <= n; i++) 
    {
        int ft;
        cin >> ft;
        adj[ft].push_back(i);
        e[i].u = ft, e[i].v = i;
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i);
    for (int i = 1; i <= n; i++)
    {
        if (col[e[i].u] == col[e[i].v]) continue;
        adn[col[e[i].u]].push_back(col[e[i].v]);
    }
    for (int i = 0; i <= cnum; i++) f[i][w[i]] = v[i];
    dfs(1);
    cout << f[1][m + 1] << endl;
    return 0;
}
2023/8/4 21:00
加载中...