详解关键路径算法

#include <iostream>
#include <vector>
using namespace std;
int eventsSize, activitiesSize;
int activitiesCostTimes[100][100];
pair<int, int> activities[100];
int eventEarlyBegin[100], eventLatestBegin[100];
int activityEarlyBegin[100], activityLatestBegin[100];void init() {memset(eventLatestBegin, 0, sizeof(eventLatestBegin));memset(eventEarlyBegin, 0, sizeof(eventEarlyBegin));memset(activityEarlyBegin, 0, sizeof(eventEarlyBegin));memset(activityLatestBegin, 0, sizeof(activityLatestBegin));
}void computeEventEarliestBegin() {eventEarlyBegin[1] = 0;int maxTimes;for (int i = 2; i <= eventsSize; ++i) {maxTimes = INT_MIN;for (int j = 1; j <= eventsSize; ++j) {if (activitiesCostTimes[j][i] != 0) {maxTimes = max(maxTimes, eventEarlyBegin[j] +activitiesCostTimes[j][i]);}}eventEarlyBegin[i] = maxTimes;}
}void computeEventLatestBegin() {eventLatestBegin[eventsSize] = eventEarlyBegin[eventsSize];int minCostTimes;for (int i = eventsSize - 1; i >= 1; --i) {minCostTimes = INT_MAX;for (int j = i; j <= eventsSize; ++j) {if (activitiesCostTimes[i][j] != 0) {minCostTimes = min(minCostTimes, eventLatestBegin[j] -activitiesCostTimes[i][j]);}}eventLatestBegin[i] = minCostTimes;}
}void computeActivityEarlyBegin() {for (int i = 1; i <= activitiesSize; ++i) {activityEarlyBegin[i] = eventEarlyBegin[activities[i - 1].first];}
}void computeActivityLatestBegin() {for (int i = 1; i <= activitiesSize; ++i) {activityLatestBegin[i] = eventLatestBegin[activities[i - 1].second] -activitiesCostTimes[activities[i - 1].first][activities[i -1].second];}
}vector<int> criticalPath() {init();computeEventEarliestBegin();computeEventLatestBegin();computeActivityEarlyBegin();computeActivityLatestBegin();vector<int> vec;for (int i = 1; i <= activitiesSize; ++i) {if (activityEarlyBegin[i] == activityLatestBegin[i]) {vec.push_back(i);}}return vec;
}int main() {cin >> eventsSize >> activitiesSize;int start, end, last;for (int i = 0; i < activitiesSize; ++i) {cin >> start >> end >> last;activitiesCostTimes[start][end] = last;activities[i] = make_pair(start, end);}vector<int> ans = criticalPath();for (int j = 0; j < ans.size(); ++j) {cout << ans[j] << " ";}cout << endl;return 0;
}

测试样例：

9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 7
5 8 5
6 8 4
7 9 2
8 9 4

详情见：

关键路径MBA
关键路径