【学习笔记】有向无环图dp
NCC79601
2019-02-23 14:12:00
采用$SPFA$思想优化，建立一个队列，把所有入度为$0$的点加入队列，每次取出队首的点并遍历子边进行$dp$，然后把子边指向结点的入度$-1$，如果入度为$0$则加入队列，重复至队列为空。复杂度$O(n)$，采用记搜也可以解决。
代码：
```cpp
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;
}
```