算法1

spfa处理循环依赖的DP，不过这题比较特殊，当一个状态更新的时候不好直接判断它能转移到的状态是否能被更新，

故需要维护一下转移方程里包含多个子状态的一项的值，否则会超时

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

typedef long long LL;

#define x first
#define y second

const int N = 200010, M = 2000010;
int h[N], e[M], ne[M], idx;
LL S[N], K[N];
LL sum[N];
int n;
queue<int> q;
LL f[N];
vector<int> dep[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%lld %lld", &S[i], &K[i]);
        int r;
        scanf("%d", &r);
        while(r --)
        {
            int k;
            scanf("%d", &k);
            add(i, k);
            dep[k].push_back(i);
        }
    }
    for(int i = 1; i <= n; ++ i) f[i] = K[i], q.push(i), st[i] = true;
    for(int u = 1; u <= n; ++ u)
    {
        sum[u] = S[u];
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            sum[u] += f[j];
        }
    }
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        if(f[t] > sum[t])
        {
;           LL tmp = f[t];
            f[t] = sum[t];
            for(auto &v: dep[t])
            {
                sum[v] -= tmp;
                sum[v] += f[t];
                if(sum[v] < f[v] && !st[v])
                {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }
    printf("%lld", f[1]);
    return 0;
}