#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define MAX_VEXTEX_NUM 40
using namespace std;

typedef struct edgenode
{
    int endvex;   /*相邻顶点在顶点表中的下标*/
    int weight;   /*边的权值*/
    struct edgenode *nextedge;   /*链字段*/
}EdgeNode,*EdgeList;  /*边表中的结点*/

typedef struct
{
    int vertex;   /*顶点*/
    EdgeList edgelist;   /*边表头指针*/
}VexNode,AdjList[MAX_VEXTEX_NUM];  /*顶点表中的结点*/

typedef struct{
    int vexnum;  /*图的顶点数*/
    int arcnum;  /*图的边的个数*/
    AdjList vexs;   /*顶点表*/
}  GraphList; /*图的邻接表表示法*/

void FindInDegree(GraphList *G,int *indegree);
int TopoSort(GraphList *G,int *ptopo);  /*拓扑排序*/
int CriticalPath(GraphList *G) ; /*关键路径*/

/*关键路径*/
int CriticalPath(GraphList *G)
{
    int i,j,k,sum=0;
    EdgeList p;
    int *ee=(int *)malloc(sizeof(int)*G->vexnum);
    int *le=(int *)malloc(sizeof(int)*G->vexnum);
    int *l=(int *)malloc(sizeof(int)*G->vexnum);
    int *e=(int *)malloc(sizeof(int)*G->vexnum);
    int *topo=(int *)malloc(sizeof(int)*G->vexnum);
    if(TopoSort(G,topo)==0)
    {
        printf("该AOV网有环!\n");
        getch();
        return(0);
    }
    /*求事件可能的最早发生时间*/
    for(i=0; i<G->vexnum; i++)
        ee[i]=0;
    for(k=0; k<G->vexnum; k++)
    {
        i=topo[k];
        p=G->vexs[i].edgelist;
        while(p!=NULL)
        {
            j=p->endvex;
            if(ee[i]+p->weight>ee[j])
                ee[j]=ee[i]+p->weight;
            p=p->nextedge;
        }
    }
    sum=ee[G->vexnum-1]; /*工程的最短完成时间*/
    for(i=0; i<G->vexnum; i++)  /*求事件允许的最迟发生时间*/
        le[i]=ee[G->vexnum-1];
    for(k=G->vexnum-2; k>=0; k--)
    {
        i=topo[k];
        p=G->vexs[i].edgelist;
        while(p!=NULL)
        {
            j=p->endvex;
            if((le[j]-p->weight)<le[i])
                le[i]=le[j]-p->weight;
            p=p->nextedge;
        }
    }
    k=0;
    printf("\n关键路径:\n");
    printf("各活动的最早发生时间依次为:\n");
    for(int q=0;q<G->vexnum;q++)
        printf("%d' '\n",ee[q]);
    printf("各活动的最晚发生时间依次为:\n");
    for(int q=0;q<G->vexnum;q++)
        printf("%d' '\n",le[q]);
    /*求活动 ak 的最早开始时间 early(k)和最晚开始时间 late(k)*/
    printf("\n|   活动   |  最早  |   最晚  |   差值  |  是否关键 ? \n");
    for(i=0;i<G->vexnum;i++)
    {
        p=G->vexs[i].edgelist;
        while(p!=NULL)
        {
            j=p->endvex;
            e[k]=ee[i];
            l[k]=le[j]-p->weight;
            printf("|  <%d,%d>   |  %4d  |  %4d  | %4d   | ",i,j,e[k],l[k],l[k]-e[k]);
            if(e[k]==l[k])
                printf("     YES"); /*输出是否关键*/
            else
                printf("     NO");
            printf("\n");
            k++;
            p=p->nextedge;
        }
    }
    printf("\n最短完成时间: %d\n",sum);  /*最短完成时间*/
    printf("\n");
    getch();
    return(1);
}
/*初始化图*/
void InitGraph(GraphList *G)
{
    int i,vexnum,arcnum,weight=0;
    int v1,v2;
    EdgeList p;
    printf("请输入顶点数和边数-->(如:x,y)\n"); /*输入顶点数和边数*/
    scanf("%d,%d",&vexnum,&arcnum); /*输入注意逗号隔开*/
    G->vexnum=vexnum;
    G->arcnum=arcnum;
    for(i=0;i<vexnum;i++)
    {
        G->vexs[i].vertex=i+1;
        G->vexs[i].edgelist=NULL;
    }
    for(i=0;i<arcnum;i++)
    {
        printf("请输入各个连接点及其权值-->(如: 1,2,10 )\n");  /*输入各个连接点及其权值*/
        scanf("%d,%d,%d",&v1,&v2,&weight);  /*输入注意逗号隔开*/
        if(v1>G->vexnum||v2>G->vexnum)
        {
            printf("你输入的节点数不符合条件!!"); /*判断输入点是否复合条件*/
            printf("\n");
            getch();
            exit(0);
        }
        p=(EdgeList)malloc(sizeof(EdgeNode));
        p->endvex=v2;
        p->weight=weight;
        p->nextedge=G->vexs[v1].edgelist;
        G->vexs[v1].edgelist=p;
    }
}
 /*拓扑排序*/
int TopoSort(GraphList *G,int *ptopo)
{
    EdgeList p;
    int i,j,k,nodeno=0,top=-1;
    int *indegree=(int *)malloc(sizeof(int)*G->vexnum);
    FindInDegree(G,indegree); /*indegree 数组赋初值*/
    for(i=0; i<G->vexnum; i++)  /* 将入度为零的顶点入栈*/
        if(indegree[i]==0)
        {   /*静态链式栈*/
            indegree[i]=top;
            top=i;
        }
        while(top!=-1)
        {
            j=top;
            top=indegree[top];  /*取当前栈顶元素并退栈*/
            ptopo[nodeno++]=j;  /*将该顶点输出到拓扑序列中*/
            p=G->vexs[j].edgelist; /*取该元素边表中的第一个边结点*/
            while(p)
            {
                k=p->endvex;
                indegree[k]--;     /*删除以该顶点为起点的边*/
                if(indegree[k]==0)
                {
                    indegree[k]=top;  /*将新的入度为零的顶点入栈*/
                    top=k;
                }
                p=p->nextedge;
            }
        }
        free(indegree);
        if(nodeno<G->vexnum)
            return(0);   /*AOV 网中存在回路*/
        else
            return(1);
}
/*求出图中所有顶点的入度*/
void FindInDegree(GraphList *G,int *indegree)
{
    int i;
    EdgeList p;
    for(i=0; i<G->vexnum; i++)
        indegree[i]=0;
    for(i=0; i<G->vexnum; i++)
    {
        p=G->vexs[i].edgelist;
        while(p)
        {
            ++indegree[p->endvex];
            p=p->nextedge;
        }
    }
}

void TopoSortMenu(void)
{
    int *ptopo;
    int i;
    GraphList *Graph=(GraphList *)malloc(sizeof(GraphList));
    InitGraph(Graph);
    ptopo=(int *)malloc(sizeof(int)*Graph->vexnum);
    if(TopoSort(Graph,ptopo)!=0)
    {
        printf("\n拓扑排序:\n");
        for(i=0;i<Graph->vexnum-1;i++)
            printf("v%d-->",ptopo[i]); /* 打印前 n-1 个 ( 有 -->)*/
        printf("v%d",ptopo[i]);  /*打印最后一个(没有-->)*/
        printf("\n\n");
    }
    else
        printf("该AOV网有环!\n");
    getch();
    free(ptopo);
    free(Graph);
}

void CriticalMenu(void)
{
    GraphList *Graph=(GraphList *)malloc(sizeof(GraphList));
    InitGraph(Graph);
    CriticalPath(Graph);
    free(Graph);
}
void TopoCriticalMenu(void)
{
    char ch;
    while(1)
    {
        printf("***************《功能菜单》****************\n");
        printf("        请选择：                           \n");
        printf("                     1.拓扑排序            \n");
        printf("                     2.关键路径            \n");
        printf("                     0.退出                \n");
        printf("*******************************************\n");
        ch=getch();
        switch(ch-'0')
        {
        case 0: exit(0);
        case 1: TopoSortMenu(); break;
        case 2: CriticalMenu(); break;
        }
    }
}

int main(void)
{
    TopoCriticalMenu();
}