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

#define MAXVEX 20
#define Status int
#define OK 1
#define ERROR 0

int* stack;
int top = 0;
int* etv;
typedef struct EdgeNode
{
    int adjvex;  //顶点下标
    int weight;  //权值
    struct EdgeNode* next;
}EdgeNode;

typedef struct VertexNode
{
    int in;//入度
    int data;//顶点
    EdgeNode *first;
}VertexNode,AdjList[MAXVEX];

typedef struct Graph
{
    AdjList adjlist;
    int numVex, numedges;//顶点和边的个数
}MGraph;

void CreateGraph(MGraph *G)
{
    printf("请输入顶点和边的个数：\n");
    scanf("%d%d", &G->numVex, &G->numedges);
    printf("请输入顶点：\n");
    for (int i = 0; i < G->numVex; i++)
    {
        scanf("%d", &G->adjlist[i].data);
        G->adjlist[i].first = NULL;
        G->adjlist[i].in = 0;//初始化入度为0
    }

    for (int k = 0; k < G->numedges; k++)
    {
        printf("请输入边（Vi，Vj)的顶点下标i，j和权值w:\n");
        int i, j, w;
        scanf("%d%d%d", &i, &j, &w);
        EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;
        e->next = G->adjlist[i].first;
        G->adjlist[i].first = e;
        G->adjlist[j].in++;//下标为j的顶点的入度+1；
    }

}

//拓扑排序
//返回ERROR说明该图不存在拓扑序列
//返回OK说明拓扑排序成功
//G为AOE网
//stack为存储拓扑序列的栈
//top指示栈stack的顶点
//etv:时间最早发生时间

Status TopoLogicalSort(MGraph *G)
{
    int* stack2=(int*)malloc(sizeof(int)*G->numVex);//存储入度为0的顶点的下标栈
    int top2 = 0;//指示Stack2的顶点
    int gettop = 0;//只是每次从stack2中弹出的顶点的下标

    //将入度为0的顶点的下标入栈
    for (int i = 0; i < G->numVex; i++)
    {
        if (G->adjlist[i].in == 0)
            stack2[++top2] = i;
    }
    //初始化事件最早发生的时间为0
    etv = (int*)malloc(sizeof(int)*G->numVex);
    for (int i = 0; i < G->numVex; i++)
    {
        etv[i] = 0;
    }

    stack = (int*)malloc(sizeof(int)*G->numVex);
    int count = 0;//记录拓扑序列中有几个点，少于顶点个数则说明拓扑排序失败，等于则成功
    while (top2) // 在位置0处没有存数据，从top2 = 1开始存的。
    {
        gettop = stack2[top2--];//弹出入度为0的点直到栈空
        count++;
        stack[++top] = gettop;
        //将该点的邻接表中的顶点入度-1
        EdgeNode *e = G->adjlist[gettop].first;
        for (; e; e = e->next)
        {
            int in = --(G->adjlist[e->adjvex].in);
            if (in == 0)
            {
                //如果入度变为0,入stack2
                stack2[++top2] = e->adjvex;
            }

            //对于已经进入拓扑序列的顶点的所有邻接点，
            //逐个计算其目前事件最早发生时间是否小于该入队的点的最早发生时间和各邻接点的权值之和
            if ((etv[gettop] + e->weight) > etv[e->adjvex])
                etv[e->adjvex] = etv[gettop] + e->weight;
        }

    }
    if (count == G->numVex)
        return OK;
    else
        return ERROR;
}

//求关键路径
void CriticalPath(MGraph *G)
{
    int gettop = 0;
    TopoLogicalSort(G);//用拓扑排序求出拓扑序列和etv;
    int *ltv = (int*)malloc(sizeof(int)*MAXVEX);
    //初始化ltv为汇点的时间
    for (int i = 0; i < G->numVex; i++)
    {
        ltv[i] = etv[G->numVex - 1];
    }
    //ltv的值=min{汇点的值-权重}
    while (top)
    {
        gettop = stack[top--];//逆序弹出拓扑序列
        EdgeNode *e = G->adjlist[gettop].first;
        for (; e; e = e->next)
        {
            if ((ltv[e->adjvex] - e->weight) < ltv[gettop])
                ltv[gettop] = ltv[e->adjvex] - e->weight;
        }
    }

    //ete值：活动的最早开工时间，就是弧的最早发生时间=
    //弧头的etv值，也就是弧头事件的最早发生时间,ete的个数是边的个数，因为边代表活动
    int ete = 0;
    //lte活动的最晚发生时间，就是不推迟工期的最晚开工时间。对于活动ai必须开始的最晚时间，
    //若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：l[i]=vl[j]-len<vk, vj>
    int lte = 0;
    for (int i = 0; i < G->numVex; i++)
    {
        EdgeNode *e = G->adjlist[i].first;
        for (; e; e = e->next)
        {
            ete = etv[i];
            lte = ltv[e->adjvex] - e->weight;
            if (ete == lte)
            {
                printf("<v%d,v%d> length: %d , ", G->adjlist[i].data, G->adjlist[e->adjvex].data, e->weight);
            }

        }
    }
}

int main()
{
    MGraph G;
    CreateGraph(&G);
    CriticalPath(&G);

    return 0;
}