拓扑排序（删边/DFS）➕AOE网关键路径

这篇博客的缘起是女鹅问的一道AOE网的题，然而上一波数据结构并没有全看完就莫名搁置了，当时看图的后半部分算法很多，想着实现一下，一直静不下心搞，就无限期搁置了（叹气，戴起老花镜开始研究= =

题目

原题
牛客网上此题的讨论
在这个讨论区看到了五花八门的答案，陷入沉思，决定自己实现一下AOE网求关键活动。

动手实现

• 首先看看这个算法详细的流程

  
  维基百科对AOE网的介绍
• 拓扑排序有删边、dfs两种实现，下面实现的是删边法（🚩dfs有空再补吧
  严格按照算法的步骤实现如下

#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>

#define MAXN 1001 // max num of vertices
#define INF 0x3f3f3f3f
using namespace std;
vector<pair<int, int >> graph[MAXN], rgraph[MAXN];
int nv, ne; // vertex 1 - nv  edge from----weight----to
int in_degree[MAXN] = {0}; // out_degree[i] = graph[i].size();
queue<int> mq; // TopologicalSort
stack<int> ms; //reverse TopologicalSort
int ve[MAXN], vl[MAXN];
map<pair<int, int>, pair<int, int>> ee_el;

// 合法输入为 无重边的有向无环图
void bulidAOE() {
    scanf("%d%d", &nv, &ne);
    int from, to, weight;
    for (int i = 0; i < ne; ++i) {
        scanf("%d%d%d", &from, &to, &weight);
        graph[from].emplace_back(to, weight);
        rgraph[to].emplace_back(from, weight);
        in_degree[to]++;
        ee_el[make_pair(from, to)] = make_pair(0, -weight);
    }
    puts("Activity On Edge Network has been built.");
    for (int i = 1; i <= nv; ++i) {
        for (auto item:graph[i]) {
            printf("V%d ---- %d ---> V%d\n", i, item.second, item.first);
        }
    }
};

/*
 * 删边法
 * queue 保存拓扑排序结果
 * 循环：选择入度为0的结点，将编号入队，删去与之相连的边（该点发出的边, 将指向的结点入度-1即可）
 * 若过程中某步找不到入度为0的结点，return false
 */
bool topologicalSort() { // if not DAG return false
    printf("TopologicalSort\n");
    bool done[MAXN] = {false};
    for (int i = 0; i < nv; ++i) {
        int curr = -1;
        for (int j = 1; j <= nv; ++j) {
            if (!done[j] && in_degree[j] == 0) {
                curr = j;
                break;
            }
        }
        if (curr == -1) {
            puts("Error! Not a DAG!");
            return false;
        }
        mq.push(curr);
        done[curr] = true;
        printf("%d - ", curr);
        for (auto item:graph[curr]) {
            in_degree[item.first]--;
        }
    }
    puts("");
    return true;
}

/*
 * 此处需要知道各结点的入边，因此最初存边的时候，不仅要存from-to，还要存to-from
 * 需要取max min 注意初始化
 * 若用邻接矩阵实现，直接遍历一列就知道有无入边了
 * 计算结点事件最早时间 ve【i】
 *      按拓扑序（queue出队）的次序，计算事件最早时间
 *      顺便将出队的结点序号入栈，以获得逆拓扑序列
 * 计算结点时间最晚时间 vl【i】
 *      按逆拓扑序（stack出栈）的次序，计算事件最晚开始时间
 *
 * 活动记作 pair<from，to>    map<pair<int, int>, pair<int, int>> ee_el;
 * 计算活动最早开始时间 ee
 * 计算活动最晚开始时间 el
 */
void calcEarlyLate() {
    fill(ve + 1, ve + nv + 1, 0);
    fill(vl + 1, vl + nv + 1, INF);
    //  calc ve
    int curr;
    if (!mq.empty()) {
        curr = mq.front();
        mq.pop();
        ms.push(curr);
        ve[curr] = 0;
    }
    while (!mq.empty()) {
        curr = mq.front();
        ms.push(curr);
        mq.pop();
        for (auto item:rgraph[curr]) {
            ve[curr] = max(ve[item.first] + item.second, ve[curr]);
        }
    }
    // calc vl
    vl[curr] = ve[curr]; // curr = ms.top()
    ms.pop();
    while (!ms.empty()) {
        curr = ms.top();
        ms.pop();
        for (auto item:graph[curr]) {
            vl[curr] = min(vl[item.first] - item.second, vl[curr]);
        }
    }
    printf("No        ve        vl\n");
    for (int i = 1; i <= nv; ++i) {
        printf("%d%10d%10d\n", i, ve[i], vl[i]);
    }
    printf("from      to        ee        el        \n");
    // calc ee and el
    for (auto &item : ee_el) {
        item.second.first = ve[item.first.first];// ee[j,k] = ve[j]
        item.second.second += vl[item.first.second]; // el[j,k] = vl[k] - weight<j-k>
        printf("%d%10d%10d%10d", item.first.first, item.first.second, item.second.first, item.second.second);
        puts(item.second.first == item.second.second ? "        Critical" : "");
    }
}

int main() {
    bulidAOE();
    if (topologicalSort()) {
        calcEarlyLate();
    }
    return 0;
}

• 把上面那道题目丢进去跑一下：

  
  运行结果
  

  ⚠️ 于是发现牛客讨论区列出ve，vl，ee，el表格的朋友答案似乎不大靠谱？？？
  似乎没一个列出正确的结果？？？
  那么这道题到底怎么才能得到正解呢？？？

正解

回到wikipedia上对整体工期的解释，它应当是源点到汇点最长路径的长度，所以要缩短工期，就是要减少最长路径（关键路径）的长度。

原题-图片
源点到汇点的路径&总长度：

• 1 —— 2 —— 4 —— 6 18
• 1 —— 2 —— 5 —— 6 18
• 1 —— 3 —— 5 —— 6 27
• 1 —— 3 —— 2 —— 4 —— 6 27
• 1 —— 3 —— 2 —— 5 —— 6 27
  后面三条为关键路径，只需找出能同时缩短他们三个的边即可。
  其实答案有很多种，因为除了1——2都是关键活动 = =
  缩短1——3可以缩短全部三条，缩短3——2可以缩短后两条，缩短5——6可以缩短第一和第三条（省略blabla）
  看选项，发现只有C满足同时缩短三条关键路径，即缩短了最长路径 #

至此，终于清爽的八达鸟～