剪贴板 6jq5z4nx - 洛谷保存站

# 关于P1273的问题（未解决）
```cpp
#include <bits/stdc++.h>
using namespace std;
// const int N = 3005;
const int N = 6;
struct Edge
{
    int to, next, w;
} e[N];
int head[N], idx = 0;
void addedge(int u, int v, int w)
{
    e[idx].to = v;
    e[idx].next = head[u];
    e[idx].w = w;
    head[u] = idx++;
}
int n, m;
int a[N];
int leaf[N], f[N][N];
void dff(int x)
{
    for (int i = head[x]; ~i; i = e[i].next)
    {
        int v = e[i].to;
        dff(v);
        leaf[x] += leaf[v];
    }
}
void dfs(int x)
{
    if (n - m + 1 <= x)
    {
        f[x][1] = a[x];
        return;
    }
    for (int i = head[x]; ~i; i = e[i].next)
    {
        int v = e[i].to;
        dfs(v);
        for (int j = leaf[x]; j >= 0; --j)
        {
            for (int k = 1; k <= min(leaf[v], j); ++k)
            {
                f[x][j] = max(f[x][j], f[v][k] - e[i].w + f[x][j - k]);
                /*想请教一下这么写为什么不对：
                f[x][j] = max(f[x][j], f[v][j - k] - e[i].w + f[x][k]);*/
            }
        }
    }
    for (int j = leaf[x] + 1; j <= m; ++j)
        f[x][j] = -0x3f3f3f3f;
}
int main()
{
    cin >> n >> m;
    memset(head, -1, sizeof head);
    for (int u = 1; u <= n - m; ++u)
    {
        int k;
        cin >> k;
        while (k--)
        {
            int t1, t2;
            cin >> t1 >> t2;
            addedge(u, t1, t2);
        }
    }
    for (int i = n - m + 1; i <= n; ++i)
        cin >> a[i];
    memset(leaf, 0, sizeof leaf);

for (int i = n - m + 1; i <= n; ++i)
        leaf[i] = 1;
    dff(1);
    memset(f, -127, sizeof f);
    for (int i = 1; i <= n; ++i)
        f[i][0] = 0;
    dfs(1);
    for (int j = m; j >= 0; --j)
    {
        if (f[1][j] >= 0)
        {
            cout << j << endl;
            return 0;
        }
    }
}
```

正在渲染内容...