128 lines
3.4 KiB
C++
128 lines
3.4 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <queue>
|
||
#include <algorithm>
|
||
#include <limits>
|
||
using namespace std;
|
||
|
||
/*
|
||
* 关键路径算法基于 AOE 网络（Activity on Edge）
|
||
* 图必须是有向无环图（DAG）
|
||
* 每条边 (u -> v) 表示一个活动，权值 w 表示活动耗时
|
||
*
|
||
* 核心步骤：
|
||
* 1. 用拓扑排序顺序计算每个事件的最早发生时间 ve[]
|
||
* 2. 逆拓扑顺序计算每个事件的最晚发生时间 vl[]
|
||
* 3. 找出所有满足 ve[u] + w == vl[v] 的活动（关键活动）
|
||
* 4. 关键活动连线形成关键路径
|
||
*/
|
||
|
||
struct Edge {
|
||
int to; // 终点事件编号
|
||
int w; // 活动耗时
|
||
};
|
||
|
||
int main() {
|
||
int n, e;
|
||
cin >> n >> e;
|
||
|
||
vector<vector<Edge>> adj(n); // 邻接表：活动在边上
|
||
vector<int> indeg(n, 0); // 各事件的入度
|
||
|
||
int u, v, w;
|
||
for (int i = 0; i < e; i++) {
|
||
cin >> u >> v >> w;
|
||
adj[u].push_back({v, w});
|
||
indeg[v]++; // 事件 v 的前置事件数加 1
|
||
}
|
||
|
||
//
|
||
// 第一步：拓扑排序，计算 ve[]
|
||
//
|
||
vector<int> topo; // 拓扑序
|
||
queue<int> q; // 用普通队列即可（要求的是顺序，不是字典序）
|
||
vector<int> ve(n, 0); // 事件最早发生时间（从起点开始的最长路径）
|
||
|
||
// 入度为 0 的事件作为起始点
|
||
for (int i = 0; i < n; i++) {
|
||
if (indeg[i] == 0) q.push(i);
|
||
}
|
||
|
||
while (!q.empty()) {
|
||
int x = q.front(); q.pop();
|
||
topo.push_back(x);
|
||
|
||
// 用此事件更新其后继事件的最早发生时间
|
||
for (auto &edge : adj[x]) {
|
||
int y = edge.to;
|
||
int cost = edge.w;
|
||
|
||
// ve[y] = max(ve[y], ve[x] + cost)
|
||
ve[y] = max(ve[y], ve[x] + cost);
|
||
|
||
// 拓扑排序削减入度
|
||
if (--indeg[y] == 0) {
|
||
q.push(y);
|
||
}
|
||
}
|
||
}
|
||
|
||
// 如果拓扑序中事件数 != n，则图中存在环
|
||
if ((int)topo.size() != n) {
|
||
cout << "The graph has a cycle. Critical path undefined." << endl;
|
||
return 0;
|
||
}
|
||
|
||
//
|
||
// 第二步：逆拓扑序，计算 vl[]
|
||
//
|
||
vector<int> vl(n, numeric_limits<int>::max());
|
||
|
||
// 终点事件的最晚时间 = 其最早时间
|
||
// 注意：可能有多个终点，因此我们取所有 ve[] 中的最大值
|
||
int maxEndTime = 0;
|
||
for (int i = 0; i < n; i++) {
|
||
maxEndTime = max(maxEndTime, ve[i]);
|
||
}
|
||
|
||
// 所有事件的最晚事件先设为 maxEndTime
|
||
for (int i = 0; i < n; i++) {
|
||
vl[i] = maxEndTime;
|
||
}
|
||
|
||
// 按拓扑序的反顺序遍历
|
||
for (int i = n - 1; i >= 0; i--) {
|
||
int x = topo[i];
|
||
|
||
// 遍历 x 的所有后继活动
|
||
for (auto &edge : adj[x]) {
|
||
int y = edge.to;
|
||
int cost = edge.w;
|
||
|
||
// vl[x] = min(vl[x], vl[y] - cost)
|
||
vl[x] = min(vl[x], vl[y] - cost);
|
||
}
|
||
}
|
||
|
||
//
|
||
// 第三步：找关键活动（关键边）
|
||
//
|
||
cout << "Critical Activities:" << endl;
|
||
|
||
for (int x = 0; x < n; x++) {
|
||
for (auto &edge : adj[x]) {
|
||
int y = edge.to;
|
||
int cost = edge.w;
|
||
|
||
// 判断活动 (x -> y) 是否关键
|
||
if (ve[x] + cost == vl[y]) {
|
||
cout << x << " -> " << y << " (cost = " << cost << ")" << endl;
|
||
}
|
||
}
|
||
}
|
||
|
||
cout << "Total project time = " << maxEndTime << endl;
|
||
|
||
return 0;
|
||
}
|