跳转至

拓扑排序⚓︎

拓扑排序（\text{Topological Sort}）是一种对有向无环图（\text{DAG}）进行线性排序的算法。它将图中的所有顶点排成一个线性序列，使得对于每一条有向边 (u, v)，顶点 u 在序列中出现在顶点 v 之前。

拓扑排序的常见实现方法有两种：基于入度的 \text{Kahn} 算法和基于深度优先搜索（\text{DFS}）的算法。

  • \text{Kahn算法}：通过计算每个顶点的入度，选择入度为零的顶点进行排序，并更新其邻接顶点的入度，直到所有顶点都被排序。
  • \text{DFS算法}：对图进行深度优先搜索，在访问完一个顶点后，将其加入结果序列中，最终将序列反转得到拓扑排序结果。
【模板】拓扑排序

给定一个有向无环图，输出其拓扑排序结果。使用 \text{Kahn} 算法实现。

C++
#include <cstdint>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n;
  cin >> n;
  vector<vector<int64_t>> g(n + 1);
  vector<int64_t> in_degree(n + 1, 0);
  for (int64_t i = 1; i <= n; i++) {
    int64_t p;
    while (cin >> p && p != 0) {
      g[i].push_back(p);
      in_degree[p]++;
    }
  }
  queue<int64_t> q;
  for (int64_t i = 1; i <= n; i++) {
    if (in_degree[i] == 0) { q.push(i); }
  }
  vector<int64_t> order;
  while (!q.empty()) {
    int64_t u = q.front();
    q.pop();
    order.push_back(u);
    for (auto v : g[u]) {
      in_degree[v]--;
      if (in_degree[v] == 0) { q.push(v); }
    }
  }
  if (order.size() != n) { return 0; }  // there is a cycle
  for (auto u : order) { cout << u << " "; }
  cout << "\n";
  return 0;
}

字典序最大/最小的拓扑排序

可以使用优先队列（\text{priority\_queue}）来实现字典序最大或最小的拓扑排序。在 \text{Kahn} 算法中，替换普通队列为优先队列，并根据需要选择最大堆或最小堆。

关键路径⚓︎

关键路径是指在有向无环图（\text{DAG}）中，从起始节点到终止节点的最长路径。关键路径通常用于项目管理和调度，以确定项目的最短完成时间。

AOV网中的关键路径⚓︎

在 \text{AOV} 网中，任务表示为顶点，任务之间的依赖关系表示为有向边，每个顶点都有一个与之关联的任务时间。通过拓扑排序，可以计算每个任务的最早开始时间和最早结束时间，从而确定关键路径。

关键路径是指从起始节点到终止节点的最长路径, 其长度表示完成所有任务所需的最短时间。关键路径上的任务是项目中最重要的任务，任何这些任务的延迟都会直接影响整个项目的完成时间。

杂务

给定一组任务及其依赖关系，计算完成所有任务所需的最短时间。

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> est(n + 1);            // earliest start time, 最早开始时间
  vector<int> eft(n + 1);            // earliest finish time, 最早结束时间
  vector<int> time(n + 1);           // task time, 任务时间
  vector<vector<int>> graph(n + 1);  // {v1,v2,...} u depends on v1,v2,...
  vector<int> visited(n + 1, 0);     // 0:not visited, 1:visiting, 2:visited

  for (int i = 1; i <= n; ++i) {
    int no, len, task;
    cin >> no;
    cin >> time[no];
    while (cin >> task) {
      if (task == 0) { break; }
      graph[no].push_back(task);
    }
  }

  auto dfs = [&](auto &&self, int u) -> void {
    visited[u] = 1;
    est[u]     = 0;
    for (int v : graph[u]) {  // u最早开始时间 = max(依赖任务最早结束时间)
      if (visited[v] == 0) {  // 还没访问过, 需要先访问依赖任务
        self(self, v);
        est[u] = std::max(est[u], eft[v]);
      } else {  // 有些任务可能被多个任务依赖, 之前已经访问过
        est[u] = std::max(est[u], eft[v]);
      }
    }
    eft[u]     = est[u] + time[u];  // u最早结束时间 = u最早开始时间 + u任务时间
    visited[u] = 2;
  };

  for (int i = 1; i <= n; ++i) {
    if (visited[i] == 0) { dfs(dfs, i); }
  }
  cout << *max_element(eft.begin() + 1, eft.end()) << '\n';
  return 0;
}

AOE网中的关键路径⚓︎

在 \text{AOE} 网中，任务表示为有向边，节点表示事件。每条边都有一个与之关联的任务时间。通过拓扑排序，可以计算每个事件的最早发生时间和最晚发生时间，从而确定关键路径。

关于关键路径的定义和计算，可以从事件和活动两个角度进行描述：

  1. 事件的最早发生时间（\text{Earliest Event Time, EET}）：事件可以发生的最早时间。事件 v 的 \text{EET} 定义为所有指向 v 的边的起始事件的 \text{EET} 加上边的权重的最大值，即 \text{EET}(v) = \max_{(u,v) \in E}(\text{EET}(u) + w(u,v))。特别地，没有入边的事件的 \text{EET} 定义为 0。
  2. 事件的最晚发生时间（\text{Latest Event Time, LET}）：事件必须发生的最晚时间，以不延误整个项目的完成时间。事件 u 的 \text{LET} 定义为所有从 u 出发的边的终止事件的 \text{LET} 减去边的权重的最小值，即 \text{LET}(u) = \min_{(u,v) \in E}(\text{LET}(v) - w(u,v))。特别地，没有出边的事件的 \text{LET} 和其 \text{EET} 相等。
  3. 关键事件：如果一个事件的 \text{EET} 等于其 \text{LET}，则该事件被称为关键事件。关键事件位于关键路径上，任何关键事件的延迟都会直接影响整个项目的完成时间。
  1. 活动的最早开始时间（\text{Earliest Start Time, EST}）：活动可以开始的最早时间。活动 (u, v) 的 \text{EST} 定义为起始事件 u 的 \text{EET}，即 \text{EST}(u, v) = \text{EET}(u)。
  2. 活动的最晚开始时间（\text{Latest Start Time, LST}）：活动必须开始的最晚时间，以不延误整个项目的完成时间。活动 (u, v) 的 \text{LST} 定义为终止事件 v 的 \text{LET} 减去活动的持续时间，即 \text{LST}(u, v) = \text{LET}(v) - w(u, v)。
  3. 关键活动：如果一个活动的 \text{EST} 等于其 \text{LST}，则该活动被称为关键活动。关键活动位于关键路径上，任何关键活动的延迟都会直接影响整个项目的完成时间。
关键路径

给定一个有向无环图，计算其关键路径上的所有事件。

C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  using PII = pair<int, int>;
  vector<vector<PII>> graph(n + 1);
  vector<vector<PII>> r_graph(n + 1);
  vector<int> in_degree(n + 1, 0);
  vector<int> r_in_degree(n + 1, 0);

  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].emplace_back(v, w);
    in_degree[v]++;
    r_graph[v].emplace_back(u, w);
    r_in_degree[u]++;
  }

  vector<int> eet(n + 1, INT32_MIN);  // earliest event time, 最早事件时间
  vector<int> let(n + 1, INT32_MAX);  // latest event time, 最晚事件时间

  queue<int> q;
  for (int i = 1; i <= n; i++) {
    if (in_degree[i] == 0) {
      q.emplace(i);
      eet[i] = 0;
    }
  }

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto [v, w] : graph[u]) {
      in_degree[v]--;
      if (in_degree[v] == 0) { q.emplace(v); }
      eet[v] = max(eet[v], eet[u] + w);
    }
  }

  q = {};
  for (int i = 1; i <= n; i++) {
    if (r_in_degree[i] == 0) {
      q.emplace(i);
      let[i] = eet[i];
    }
  }

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto [v, w] : r_graph[u]) {
      r_in_degree[v]--;
      if (r_in_degree[v] == 0) { q.push(v); }
      let[v] = min(let[v], let[u] - w);
    }
  }

  vector<int> critical;
  for (int i = 1; i <= n; i++) {
    if (eet[i] == let[i]) { critical.push_back(i); }
  }
  sort(critical.begin(), critical.end());
  cout << critical.size() << "\n";
  for (auto v : critical) { cout << v << " "; }
  cout << "\n";
  return 0;
}

评论