输入有向无环图的相关信息，求关键路径。 算法思路： （1）使用邻接表存储图。邻接表的每个链表中，要求按顶点的序号从大到小排列； （2）求DAG图的拓扑排序序列，使用栈辅助操作，初始时，入度为0的顶点入栈时，也按顶点的序号从大到小的顺序入栈； （3）求每个事件的最早发生时间ve(i)； （4）求每个事件的最迟发生时间vl(i)； （5）求每个活动的最早开始时间e(i)和最迟开始时间l(i)，若e(i)等于l(i)，则此活动为关键活动。 输入说明： 输入有向图的顶点数、边数、各顶点的值，各边的信息。 输出说明： 输出所有关键活动，两个顶点用逗号间隔，且用尖括号括起来。所有标点符号为英文标点符号。 注意，因邻接表中链表内的按顶点的序号从大到小排列，所以会有如下输出顺序： ...... <4,7> <4,6> ...... 输入样例： 9 11 0 1 2 3 4 5 6 7 8 0 1 6 0 2 4 0 3 5 1 4 1 2 4 1 3 5 2 4 6 9 4 7 7 5 7 4 6 8 2 7 8 4 输出样例： <0,1> <1,4> <4,7> <4,6> <6,8> <7,8>

以下是C语言的代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTICES 1000
#define MAX_EDGES 10000

typedef struct EdgeNode EdgeNode;
struct EdgeNode {
    int vertex;
    int weight;
    EdgeNode *next;
};

typedef struct VertexNode VertexNode;
struct VertexNode {
    int value;
    EdgeNode *head;
};

typedef struct Graph Graph;
struct Graph {
    int num_vertices;
    int num_edges;
    VertexNode vertices[MAX_VERTICES];
};

typedef struct Stack Stack;
struct Stack {
    int top;
    int data[MAX_VERTICES];
};

void init_graph(Graph *graph, int num_vertices)
{
    graph->num_vertices = num_vertices;
    graph->num_edges = 0;
    for (int i = 0; i < num_vertices; i++) {
        graph->vertices[i].value = i;
        graph->vertices[i].head = NULL;
    }
}

void add_edge(Graph *graph, int start, int end, int weight)
{
    EdgeNode *new_node = (EdgeNode *)malloc(sizeof(EdgeNode));
    new_node->vertex = end;
    new_node->weight = weight;
    new_node->next = graph->vertices[start].head;
    graph->vertices[start].head = new_node;
    graph->num_edges++;
}

void print_path(int path[], int start, int end)
{
    if (start == end) {
        printf("%d", start);
    } else {
        print_path(path, start, path[end]);
        printf(" -> %d", end);
    }
}

void topological_sort(Graph *graph, int ve[], Stack *stack)
{
    int indegree[MAX_VERTICES] = {0};
    for (int i = 0; i < graph->num_vertices; i++) {
        EdgeNode *p = graph->vertices[i].head;
        while (p != NULL) {
            indegree[p->vertex]++;
            p = p->next;
        }
    }

    for (int i = graph->num_vertices - 1; i >= 0; i--) {
        if (indegree[i] == 0) {
            stack->data[++stack->top] = i;
        }
    }

    while (stack->top >= 0) {
        int vertex = stack->data[stack->top--];
        EdgeNode *p = graph->vertices[vertex].head;
        while (p != NULL) {
            int w = p->weight;
            if (ve[vertex] + w > ve[p->vertex]) {
                ve[p->vertex] = ve[vertex] + w;
            }
            if (--indegree[p->vertex] == 0) {
                stack->data[++stack->top] = p->vertex;
            }
            p = p->next;
        }
    }
}

void critical_path(Graph *graph)
{
    int ve[MAX_VERTICES] = {0};
    int vl[MAX_VERTICES] = {0};
    int path[MAX_VERTICES] = {0};
    Stack stack = {-1};

    topological_sort(graph, ve, &stack);

    for (int i = 0; i < graph->num_vertices; i++) {
        vl[i] = ve[graph->num_vertices - 1];
    }

    while (stack.top >= 0) {
        int vertex = stack.data[stack.top--];
        EdgeNode *p = graph->vertices[vertex].head;
        while (p != NULL) {
            int w = p->weight;
            if (vl[p->vertex] - w < vl[vertex]) {
                vl[vertex] = vl[p->vertex] - w;
            }
            p = p->next;
        }
    }

    for (int i = 0; i < graph->num_vertices; i++) {
        EdgeNode *p = graph->vertices[i].head;
        while (p != NULL) {
            int e = ve[i];
            int l = vl[p->vertex] - p->weight;
            if (e == l) {
                printf("<%d,%d> ", i, p->vertex);
            }
            p = p->next;
        }
    }
}

int main()
{
    int num_vertices, num_edges;
    Graph graph;

    scanf("%d %d", &num_vertices, &num_edges);
    init_graph(&graph, num_vertices);

    for (int i = 0; i < num_vertices; i++) {
        int value;
        scanf("%d", &value);
        graph.vertices[i].value = value;
    }

    for (int i = 0; i < num_edges; i++) {
        int start, end, weight;
        scanf("%d %d %d", &start, &end, &weight);
        add_edge(&graph, start, end, weight);
    }

    critical_path(&graph);

    return 0;
}