有环的图可以考虑缩点转化成树

懵逼的 题目

传送至 BZOJ

扯淡的 题解

乍一看woc这不是选课嘛? 还省选?(flag * 1)
然后他们说可能会有环要用缩点
emmmm…那也很水啊把两个程序拼起来就行了(flag * 2)
然后…
20
发现没有处理 [当前节点不能选但是兄弟可以选] 的情况(选课的话因为费用都是 1 不会GG)
40
发现没有处理好环…没有把缩完点的环和 root 连起来

剩下就没什么好说的了…
就是选课魔改 × tarjan缩点

沙茶的 代码

//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (100 + 5)
#define MAXM (500 + 5)
#define MAXW (100000 + 5)
#define MAXV (50000 + 5)
#define INF (10000000 + 5)
#define MNULL (100 + 3)
const int root = 0;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
} b[MAXN];
int g[MAXN];
int cntb;

struct node
{
    int right;
    int left;
} a[MAXN];

int n;
int m;
int w[MAXN];
int v[MAXN];

int fa[MAXN];
int wn[MAXN];
int vn[MAXN];

int dfn[MAXN];
int low[MAXN];
int cntd;
stack<int> s;
bool instack[MAXN];

int ans;

int f[MAXN][MAXV];

void init();
void adn(int, int);
void tarjan(int);
void inite();
void adnn(int, int);
void solve();
int dfs(int, int);
int main()
{
    init();
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
        {
            tarjan(i);
        }
    }
    inite();
    solve();
    printf("%d", ans);
    return 0;
}

void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}

void init()
{
    memset(instack, false, sizeof(instack));
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++)
    {
        a[i].left = a[i].right = MNULL;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
    }
    int srx;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &srx);
        adn(srx, i);
    }
}

void tarjan(int dq)
{
    low[dq] = dfn[dq] = ++cntd;
    s.push(dq);
    instack[dq] = true;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (!dfn[b[i].to])
        {
            tarjan(b[i].to);
            low[dq] = min(low[dq], low[b[i].to]);
        }
        else if (instack[b[i].to])
        {
            low[dq] = min(low[dq], dfn[b[i].to]);
        }
    }
    if (low[dq] == dfn[dq])
    {
        while (!s.empty() && s.top() != dq)
        {
            int& x = s.top();
            fa[x] = dq;
            instack[x] = false;
            s.pop();
        }
        if (!s.empty())
        {
            s.pop();
            fa[dq] = dq;
            instack[dq] = false;
        }
    }
}

void inite()
{
    bool visited[MAXN];
    memset(visited, false , sizeof(visited));
    for (int i = 1; i <= n; i++)
    {
        vn[fa[i]] += v[i];
        wn[fa[i]] += w[i];
        if (fa[b[i].from] != fa[b[i].to])
        {
            adnn(fa[b[i].from], fa[b[i].to]);
            visited[fa[b[i].to]] = true;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!visited[fa[i]])
        {
            adnn(0, fa[i]);
            visited[fa[i]] = true;
        }
    }
}

void adnn(int from, int to)
{
    if (a[from].left == MNULL)
    {
        a[from].left = to;
    }
    else
    {
        int x;
        x = a[from].left;
        while (a[x].right != MNULL)
        {
            x = a[x].right;
        }
        a[x].right = to;
    }
}

void solve()
{
    memset(f, -1, sizeof(f));
    /*for (int i = 0; i <= m; i++)
    {
        f[root][i] = 0;
    }*/
    /*for (int i = 1; i <= m; i++)
    {
        ans = max(ans, dfs(root, i));
    }*/
    ans = dfs(root, m);
}

int dfs(int dq, int dqm)
{
    if (dqm < 0)// dqm < 0: GG
    {
        return -INF;
    }
    if (f[dq][dqm] != -1)// 已经访问过 
    {
        return f[dq][dqm];
    }
    if (dq == MNULL || (dqm == 0 && vn[dq] != 0))// 访问到空, 或者dqm == 0 
    {
        return f[dq][dqm] = 0;
    }
    f[dq][dqm] = (dqm >= vn[dq]) ? wn[dq] : 0;// 能否选当前节点 
    f[dq][dqm] = max(f[dq][dqm], dfs(a[dq].right, dqm));// 全部都选兄弟 
    if (dqm >= vn[dq])
    {
        f[dq][dqm] = max(f[dq][dqm], dfs(a[dq].left, dqm - vn[dq]) + wn[dq]);// 全部都选儿子 
        for (int i = 0; i <= dqm - vn[dq]; i++)
        {
            f[dq][dqm] = max(f[dq][dqm], dfs(a[dq].left, i) + dfs(a[dq].right, dqm - vn[dq] - i) + wn[dq]);// i 个选儿子, 剩下的选兄弟, 当然还要选自己 
        }
    }
    return f[dq][dqm];
}

/*
3 10
5 5 6
2 3 4
0 1 1


5
*/

/*
8 6
5 2 1 1 2 3 10 1
1 5 6 7 8 5 1 8
0 1 1 2 2 2 3 0


9
*/


/*
6 20
5 5 5 1 10 5
1 1 1 100 5 5
2 3 1 2 0 5


103
*/

By 逃课一时爽的 Cansult

附: 我们今天语文连堂老师不在, 就变成一节正课一节活动课, 本来想逃活动课结果逃了正课…CTL