实现关键路径算法,c++

好的，以下是实现关键路径算法的C++代码：

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const int MAXN = 10005; // 最大节点数
vector<pair<int, int>> G[MAXN]; // 邻接表存图
int inDegree[MAXN];     // 入度数组
int earliest[MAXN];     // 记录最早开始时间
int latest[MAXN];       // 记录最晚开始时间
int duration[MAXN];     // 记录每个节点的持续时间

void topologicalSort(int n)
{
    queue<int> q;
    memset(earliest, 0, sizeof(earliest)); // 初始化最早开始时间为0

    for(int i=1; i<=n; i++)
        if(inDegree[i] == 0) // 将所有入度为0的节点入队
            q.push(i);

    while(!q.empty())
    {
        int u = q.front();
        q.pop();

        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i].first;
            int w = G[u][i].second;
            inDegree[v]--; // 将u -> v这条边删除

            if(inDegree[v] == 0) // 如果入度为0，则入队
                q.push(v);

            earliest[v] = max(earliest[v], earliest[u]+w); // 更新最早开始时间
        }
    }
}

void criticalPath(int n)
{
    topologicalSort(n);
    memset(latest, earliest[n], sizeof(latest)); // 初始化最晚开始时间为最早开始时间

    for(int u=n; u>=1; u--) // 倒序遍历每个节点
        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i].first;
            int w = G[u][i].second;

            latest[u] = min(latest[u], latest[v]-w); // 更新最晚开始时间
        }

    for(int u=1; u<=n; u++)
        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i].first;
            int w = G[u][i].second;

            if(latest[v]-w == earliest[u]) // 如果u -> v是关键路径上的边，则输出
                cout << u << " -> " << v << endl;
        }
}

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

    for(int i=0; i<m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(make_pair(v, w)); // 添加一条有向边u -> v
        inDegree[v]++;       // 节点v的入度加1
        duration[u] = w;     // 记录节点u的持续时间
    }

    criticalPath(n); // 进行关键路径算法

    return 0;
}

以上代码中，`G`是邻接表，`inDegree`是入度数组，`earliest`记录最早开始时间，`latest`记录最晚开始时间，`duration`记录每个节点的持续时间，`topologicalSort`函数实现了拓扑排序算法并计算最早开始时间，`criticalPath`函数实现了关键路径算法。在`main`函数中读入了节点数`n`和有向边数`m`，并将所有有向边添加到邻接表中，同时更新每个节点的入度和持续时间。最后调用`criticalPath`函数进行关键路径算法，输出关键路径上的边。