To boldly go where no one has gone before.

【学习笔记】有向无环图dp

2019-02-23 14:12:00


采用$SPFA$思想优化,建立一个队列,把所有入度为$0$的点加入队列,每次取出队首的点并遍历子边进行$dp$,然后把子边指向结点的入度$-1$,如果入度为$0$则加入队列,重复至队列为空。复杂度$O(n)$,采用记搜也可以解决。

代码:

void toposort() {
    queue<int> q;
    for(int i=1; i<=n; i++)
        if(!in[i]) {
            q.push(i);
            f[i] = p[i];
        }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=last[u]; i; i=edge[i].next) {
            int v = edge[i].to;
            f[v] = max(f[v], f[u]+p[v]);
            in[v]--;
            if(!in[v])
                q.push(v);
        }
    }
    return;
}