用C语言写一个求解关键路径函数

由于关键路径算法较为复杂，需要使用图论中的拓扑排序和动态规划的思想，因此代码较长。以下是一个使用C语言实现的求解关键路径的函数：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE 1000
#define MAX_EDGE 10000
#define INF 0x3f3f3f3f

typedef struct Edge {
    int from, to, weight;
} Edge;

int node_num, edge_num;
int head[MAX_NODE], nxt[MAX_EDGE], to[MAX_EDGE], weight[MAX_EDGE], cnt;
int in_degree[MAX_NODE], out_degree[MAX_NODE], earliest[MAX_NODE], latest[MAX_NODE];
int queue[MAX_NODE], front, rear;

void add_edge(int u, int v, int w) {
    nxt[++cnt] = head[u];
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt;
}

void topo_sort() {
    front = 0, rear = -1;
    for (int i = 1; i <= node_num; i++)
        if (in_degree[i] == 0)
            queue[++rear] = i;
    while (front <= rear) {
        int u = queue[front++];
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i], w = weight[i];
            in_degree[v]--;
            if (in_degree[v] == 0)
                queue[++rear] = v;
            earliest[v] = earliest[u] + w;
        }
    }
}

int critical_path() {
    memset(in_degree, 0, sizeof(in_degree));
    memset(out_degree, 0, sizeof(out_degree));
    memset(earliest, 0, sizeof(earliest));
    memset(latest, INF, sizeof(latest));
    memset(head, 0, sizeof(head));
    memset(nxt, 0, sizeof(nxt));
    memset(to, 0, sizeof(to));
    memset(weight, 0, sizeof(weight));
    cnt = 0;
    scanf("%d %d", &node_num, &edge_num);
    for (int i = 0; i < edge_num; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        in_degree[v]++;
        out_degree[u]++;
    }
    topo_sort();
    int end_node = 1;
    for (int i = 2; i <= node_num; i++)
        if (earliest[i] > earliest[end_node])
            end_node = i;
    latest[end_node] = earliest[end_node];
    rear = -1;
    for (int i = 1; i <= node_num; i++)
        if (out_degree[i] == 0)
            queue[++rear] = i;
    while (front <= rear) {
        int u = queue[front++];
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i], w = weight[i];
            out_degree[u]--;
            if (out_degree[u] == 0)
                queue[++rear] = u;
            if (latest[v] - w < latest[u])
                latest[u] = latest[v] - w;
        }
    }
    int ans = 0;
    for (int i = 1; i <= node_num; i++)
        for (int j = head[i]; j; j = nxt[j]) {
            int u = i, v = to[j], w = weight[j];
            if (earliest[u] + w == earliest[v] && latest[v] - w == latest[u])
                if (ans < earliest[u] + w)
                    ans = earliest[u] + w;
        }
    return ans;
}

int main() {
    printf("%d\n", critical_path());
    return 0;
}

函数中主要使用了拓扑排序和动态规划的思想来求解关键路径，具体实现如下：

1. 定义了一个结构体`Edge`来存储边的起点、终点和权重。
2. 声明了一些全局变量，包括节点数、边数、邻接表、入度、出度、最早开始时间和最晚开始时间等。
3. 实现了添加边的函数`add_edge`，用于向邻接表中加入一条边。
4. 实现了拓扑排序的函数`topo_sort`，用于求出每个节点的最早开始时间。
5. 实现了求解关键路径的函数`critical_path`，在函数中使用了拓扑排序求出每个节点的最早开始时间和最晚开始时间，从而求出关键路径和关键路径长度。
6. 在`main`函数中调用`critical_path`函数并输出结果。

值得注意的是，函数中使用了队列来实现拓扑排序，其中用`front`和`rear`来表示队列的头和尾，用`queue`数组来存储队列中的元素。同时，为了方便起见，代码中使用了邻接表来存储图的信息。