一、基础知识

1. AOV 网

AOV 网：以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为顶点表示活动的网（Activity On Vertex Network），简称 AOV 网。

2. 拓扑序列

设 $G=(V,E)$ 是一个具有 $n$ 个顶点的有向图，$V$ 中的顶点序列 $v_1,v_2,\cdots ,v_n$，满足若从顶点 $v_i$ 到 $v_j$ 有一条路径，则在顶点序列中顶点 $v_i$ 必在顶点 $v_j$ 之前。

3. 拓扑排序

构造拓扑序列的过程，每个图的拓扑排序不一定唯一。

4. 拓扑排序方法

1. 从 AOV 网中选择一个没有前驱（入度为 $0$ 的点，无依赖）的顶点，并输出；
2. 从 AOV 网中去掉该顶点以及以该顶点为出发点的所有边；
3. 重复上述过程，直到 AOV 网中的不存在入度为 $0$ 的顶点。

5. 判断有无回路

完成 $3$ 后，如果 AOV 网中还有顶点，说明有回路；反之，说明所有顶点都被输出，即没有回路。

6. DAG 图

有向无环图（DAG，Directed Acycline Graph）是树的泛化，和树具有类似的层次性。
因为 DAG 图由于具有层次性，因此具有无后效性。一些实际问题中的二元关系都可使
用 DAG 来建模，从而将这些问题转化为 DAG 上的最长（短）路问题。

拓扑排序是一个可以把所有的顶点排序的算法，它排序的依据是深度优先搜索算法的完成时间。可以根据拓扑排序来计算有向无环图（的单源最短路径），因为拓扑排序正好是建立在无环的基础上，在这个图中没有负权重边以及回路边。

拓扑排序是将图中所有顶点排成一个线性序列，使得图中任意一对顶点 $u,v$，若边 $(u,v)\in E(G)$，则 $u$ 在线性序列中出现在 $v$ 之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

对于一个 DAG，可以这样确定一个图中顶点的顺序：对于所有的 $u,v$，若存
在有向路径 u->v，则在最后的顶点排序中 $u$ 就位于 $v$ 之前。这样确定的顺序
就是一个 DAG 的拓扑排序。
拓扑排序的特点如下：
1）所有可以到达顶点 $v$ 的顶点 $u$ 都位于顶点 $v$ 之前；
2）所有从顶点 $v$ 可以到达的顶点 $u$ 都位于顶点 $v$ 之后另外，只有有向无环图才存在拓扑排序，一个图的拓扑顺序不唯一。

7. 拓扑排序模板

bool topoSort(){
    queue<int>que;//存储所有入度为 0 的点
    for(int i=1;i<=n;i++)
        if(inDeg[i]==0)
            que.push(i);
    int cnt=0;//删除过的点的个数
    while(!que.empty()){
        int u=que.front();
        que.pop();//删除目前入度为 0 的点
        cnt++;
        //将以 u 为出发点的所有点删除
        for(int v:edges[u]){
            inDeg[v]--;
            if(inDeg[v]==0)
                que.push(v);
        }
    }
    return cnt==n;
}

二、基础应用

1. 最大食物链计数

1.1 审题

题目描述

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。
给你一个食物网，你要求出这个食物网中最大食物链的数量。（这里的"最大食物链"，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 $1$ 秒的时间。由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

输入格式

第一行，两个正整数 $n,m$，表示生物种类 $n$ 和吃与被吃的关系数 $m$。
接下来 $m$ 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

1.2 分析

按照样例举例：

5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

递推公式：很显然，一个点必然是其所有依赖点的食物链个数之和，例如：

如图，$A$ 结束有一个食物链，$B$ 结束有一个食物链，$C$ 结束有两个食物链。
假如有多个顶端的猎食者，需要有一个更加顶端的猎食者（就是人类）将他们相加，可以构造一个虚点，方便输出。

1.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e3+8;
const int MOD=80112002;
int n,m,inDeg[MAXN],outDeg[MAXN],dp[MAXN];//dp[u]:以u结尾的食物链个数
vector<int>edges[MAXN];
void topoSort(){
    queue<int>que;
    for(int i=1;i<=n;i++)
        if(inDeg[i]==0){
            que.push(i);
            dp[i]=1;
        }
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(int v:edges[u]){//u->v
            dp[v]=(dp[v]+dp[u])%MOD;//相当于所有依赖点的食物链个数之和
            inDeg[v]--;
            if(!inDeg[v])
                que.push(v);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        edges[u].push_back(v);//u->v
        inDeg[v]++;
        outDeg[u]++;
    }
    for(int i=1;i<=n;i++)//构造虚点
        if(outDeg[i]==0){//所有食物链的顶端都连接到虚点
            edges[i].push_back(n+1);
            inDeg[n+1]++;
            outDeg[i]++;
        }
    n++;
    topoSort();
    cout<<dp[n];
    return 0;
}

2. Test for Job

2.1 审题

题目描述

Mr.Dog 想要找一份工作赚钱养家，但是在应聘时遇到了这样一个测试：
给定一张地图，上面给出了城市之间的单向道路（该地图没有重边和环），每个城市都有一个权值，当你到达一个城市时，你会获得该城市的权值（注意该权值可能为负）。
起点是入度为 $0$ 的城市，即没有城市能到达该城市；终点是出度为 $0$ 的城市，即该城市不能到达其他城市。现在 Mr.Dog 的任务是从一个起点出发，到达一个终点，通过这条路径它能获得最大的权值。
也就是说，如果存在多个起点和终点，Mr.dog 可以随意选择一个起点和一个终点，并使自己获得的权值和尽可能大。
注意，如果一个孤立的点存在的话，它既是起点也是终点，这条路线上的权值和就是它自己的权值。

输入格式

第一行两个整数 $N(1\le N\le 10^5)$和 $M(1\le M\le 10^6)$，表示城市的个数和道路的个数。
接下来 $N$ 行，每行一个整数 $a_i(|a_i|\le 20000)$ 表示城市 $i$ 的权值。
接下来 $M$ 行，每行两个整数 $x,y$，表示城市 $x$ 到 $y$ 有一条单向边。

输出格式

请输出一个整数，表示 Mr.Dog 能获得的最大权值。

2.2 分析

同样也是一道模板题，需要掌握之前学过的一个路径采集的 dp 模板。其他都是拓扑排序的模板。

2.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int NEGINF=0xc0c0c0c0;
int n,m,wt[MAXN],inDeg[MAXN],outDeg[MAXN],dp[MAXN];
vector<int>edges[MAXN];
void topoSort(){
    queue<int>que;
    for(int i=1;i<=n;i++)
        if(inDeg[i]==0){
            que.push(i);
            dp[i]=wt[i];
        }
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(int v:edges[u]){
            dp[v]=max(dp[v],dp[u]+wt[v]);//看本身大还是加上前面走过的最大
            inDeg[v]--;
            if(!inDeg[v])que.push(v);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>wt[i];
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        edges[u].push_back(v);
        inDeg[v]++;
        outDeg[u]++;
    }
    memset(dp,NEGINF,sizeof(dp));
    for(int i=1;i<=n;i++)//构造虚点
        if(outDeg[i]==0){
            edges[i].push_back(n+1);
            inDeg[n+1]++;
            outDeg[i]++;
        }
    n++;
    topoSort();
    cout<<dp[n];
    return 0;
}

三、拓展应用

1. 巧克力牛奶

1.1 审题

农民约翰的牛奶生产和运输是一个复杂的过程，他用挤奶器给他的若干头奶牛挤奶，然后流入管道。
每一个管道把一台挤奶器和一个接口连接起来，每个接口可能连有一台或多台挤奶器（这样几个管道里的牛奶就汇合了）。然后牛奶通过附加管道（连在各个接口之间的管道）直到流到中央管道，通向储存室。 然后这些牛奶反过来通过管道分流到各个牛奶桶，最后被运至市场。
约翰发现对于牛奶来说，最多只有一种方式从一个接口流到另一个接口。并且由于约翰是一个高效率的人，他需要确保每一个管道都有牛奶经过，也就是说，没有多余的管道。
如果我们把每个挤奶机、接口和奶罐都看成一个节点，就共有 $N$ 个节点，输入有序的节点对 $A_i$ 和 $B_i$，代表牛奶从 $A_i$ 节点流到 $B_i$ 节点。如果没有相对应的头节点，那就说明这是一个挤奶器，同样的如果没有对应的尾节点，则这是一个奶罐。
这几个月巧克力牛奶的需求量激增，所以约翰想要在某一个接口处安装一个巧克力混合器，把所有牛奶都变成巧克力牛奶，为了节约，约翰只买了一个巧克力混合器。所以他想把这个东西放到一个所有牛奶都能经过的接口，保证一定有这种接口存在。
请你帮助约翰找到这样的节点（注意：不能把巧克力混合器放在挤奶机里）。

1.2 分析

找到几个点，可以将所有的牛奶都汇集到那几个点上。例如：

其中点 $6,7$ 是可以放巧克力混合器的：

程序的变量/数组含义：
$n$：表示节点的总数，也就是牛奶的生产、运输和存储过程中的所有节点数。
$m$：表示附加管道的总数。
inDeg[]：用于记录每个节点的入度，也就是流入该节点的管道数量。
dp[]：用于记录每个节点所能接收的牛奶的数量。
isSt[]：用于记录每个节点是否已经被判断为可以放置巧克力混合器的节点。
edges[][]：用于存储每个节点的出度的结点，也就是从该节点出发的管道所连接的节点。
ans[]：用于存储所有可以放置巧克力混合器的节点。

1.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,m,inDeg[MAXN],dp[MAXN];
bool isSt[MAXN];
vector<int>edges[MAXN],ans;
void topoSort(){
    int stCnt=0;
    queue<int>que;
    for(int i=1;i<=n;i++)
        if(inDeg[i]==0){
            que.push(i);
            dp[i]=1;
            isSt[i]=1;
            stCnt++;
        }
    while(!que.empty()){
        int u=que.front();
        que.pop();
        if(!isSt[u]&&dp[u]==stCnt)
            ans.push_back(u);
        if(edges[u].size()!=1)break;
        int v=edges[u][0];//u->v
        dp[v]+=dp[u];//奶量
        inDeg[v]--;
        if(inDeg[v]==0)
            que.push(v);
    }
}
int main(){
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        edges[u].push_back(v);
        inDeg[v]++;
    }
    topoSort();
    sort(ans.begin(),ans.end());
    for(int i:ans)cout<<i<<endl;
    return 0;
}

2. 车站分级

2.1 审题

一条单向的铁路线上，依次有编号为 $1\sim n$ 的 $n$ 个火车站。每个火车站都有一个级别，最低为 $1$ 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 $x$，则始发站、终点站之间所有级别大于等于火车站 $x$ 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是 $5$ 趟车次的运行情况。其中，前 $4$ 趟车次均满足要求，而第 $5$ 趟车次由于停靠了 $3$ 号火车站（$2$ 级）却未停靠途经的 $6$ 号火车站（亦为 $2$ 级）而不满足要求。

现有 $m$ 趟车次的运行情况（全部满足要求），试推算这 $n$ 个火车站至少分为几个不同的级别。

2.2 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
int n,m,mx,dp[MAXN],inDeg[MAXN],adj[MAXN][MAXN];
void toposort(){
    queue<int>que;
    for(int i=1;i<=n;i++)
        if(inDeg[i]==0){
            dp[i]=1;
            que.push(i);
        }
    while(!que.empty()){
        int u=que.front();
        que.pop();
        mx=max(mx,dp[u]);
        for(int v=1;v<=n;v++)
            if(adj[u][v]){
                dp[v]=max(dp[v],dp[u]+1);
                inDeg[v]--;
                if(inDeg[v]==0)que.push(v);
            }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1,k;i<=m;i++){
        cin>>k;
        vector<int>stops;//停车点
        bool isLine[MAXN]={};//火车运行线路停靠点
        for(int j=1,v;j<=k;j++){
            cin>>v;
            stops.push_back(v);
            isLine[v]=true;
        }
        for(int u=stops.front();u<=stops.back();u++)
            for(int v:stops)
                if(!isLine[u]&&adj[u][v]==0)
                    adj[u][v]=1,inDeg[v]++;
    }
    toposort();
    cout<<mx;
    return 0;
}