手动博客搬家: 本文发表于20180716 10:49:04, 原地址

首先，感谢以下几位大佬们在此问题上对我的帮助：本市大佬sdqd01, 外省大佬ez_dc, coconight, szlhx01, jxgz03 (均为某OJ用户名)

一、基本概念

有向无环图 (Directed Acyclic Graph, DAG): 没有环的有向图。

Tarjan算法缩点、拓扑排序

在有向无环图上，可以进行动态规划来求解问题，具体见后面的例题。

二、问题引入

一切都要从半年前说起：

半年前我正在准备地理生物中考，其中生物有这样一种题：

给一个食物网（当然是DAG啦），求该食物网里一共有几条食物链。

当时同学们的做法是：枚举每一条食物链。

先不考虑是否符合生物学原理，最坏情况下的复杂度？

\(O(n2^{n-2})\) (把边全连满)

但是我们可以\(DP\)！

我的做法：令\(dp[i]\)表示以\(i\)结束（或称为在\(i\)处汇聚）的食物链条数。（食物链都是从被捕食者向捕食者连有向边）

则转移为：\(dp[i]=\sum_{j\in ind[i]}dp[j]\), 其中\(ind[i]\)为连向\(i\)的点的集合。

初始状态：\(dp[生产者]=1\), 生产者即入度为0的点。

答案：\(ans=\sum dp[最高级消费者]\)，最高级消费者即出度为0的点。

但是一个问题是：如果我们用代码实现这个过程，如何确定dp的顺序？

很显然，一个点的\(dp\)值能够被确定，其先决条件是它的所有入点的\(dp\)值都已被确定。因此我们需要确定一个点的排列，使得每个点的所有入点都在这个点之前出现。这里用到拓扑排序。拓扑序就是我们\(DP\)的顺序。

那这样的话，先拓扑排序，记下来拓扑序列，然后从前往后DP？

其实还不用。我们可以直接一边拓扑排序一边DP，就是每\(BFS\)访问到一个节点\(i\)，我们枚举\(i\)的所有出度，对于\(i\)的一个出度\(j\), 删掉\(i\)到\(j\)的边 (拓扑排序)同时用\(dp[i]\)更新\(dp[j]\) (DP).

一边拓扑排序，一边dp，既省空间又省代码。

复杂度？\(n\)个点\(m\)条边的话，\(O(n+m)\).

现在，假定这个图一定是DAG. 对于不是DAG的情况，将在后面讨论。

三、例题

1. codeforces 919D ()

2. bzoj 1924 ()
   首先，这道题难点在建图，这个过程不是本文的重点，不再赘述。
   假设我们已经建出了图。现在我们需要求图上的最长链。有以下三种方法：

(1) SPFA跑最长路。 (2) DP. 有BFS和DFS两种方法。

DP做法(BFS)：令\(dp[i]\)表示到i为止最长链的长度，则有\(dp[i]=\max_{j\in ind[i]} dp[j]+1\)，按拓扑序转移即可。

等等？建出的图上可能有环？

此时答案显然不能是\(\inf\), 因为在本题中走过一个点多次只会统计一次答案。所以我们必须通过Tarjan算法来缩点，将每个强连通分量缩成一个点，点的权值为强连通分量的大小。这样的话，如果题目里的Henry沿最长链走到了这个强连通分量中的一个点，则此时如果顺道把这个强连通分量访问遍，答案显然不会更差。缩完点之后，变成了\(DAG\)，然后就可以\(DP\)啦。

但是！除了BFS，我们还有一种更简单的\(DP\)方法，即\(DFS\)！时间复杂度一样，BFS20行左右，DFS不到10行，而且省一点空间

具体做法：令\(dp[i]\)为从i 开始的最长链。代码如下：

void dfs(int u,int prv){    if(dp[u]-a[u]>0) return;    dp[u] = a[u];    for(int i=fe0[u]; i; i=e0[i].nxt)    {        dfs(e0[i].v,u);        dp[u] = max(dp[u],dp[e0[i].v]+a[u]);    }}

是不是特别简洁！不需要冗长的拓扑排序！

但是它是如何保证转移顺序的呢？

由于是从i开始，因此转移顺序应是每个点的所有出边连向的点转移后才转移这个点，而代码中的for循环恰恰保证了这一点。

整道题代码：(dfs)

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 300000;const int M = 1200000;const int C = 1000000;struct Edge{    int v,nxt; bool us;} e[M+2],e0[M+2];struct Node{    int x,y,z;    bool operator <(const Node &arg) const    {        return y