这篇博客的缘起是女鹅问的一道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 —— 618 -
1 —— 2 —— 5 —— 618 -
1 —— 3 —— 5 —— 627 -
1 —— 3 —— 2 —— 4 —— 627 -
1 —— 3 —— 2 —— 5 —— 627
后面三条为关键路径，只需找出能同时缩短他们三个的边即可。
其实答案有很多种，因为除了1——2都是关键活动 = =
缩短1——3可以缩短全部三条，缩短3——2可以缩短后两条，缩短5——6可以缩短第一和第三条（省略blabla）
看选项，发现只有C满足同时缩短三条关键路径，即缩短了最长路径 #
