#include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #define MAX 9

 #define ERROR 1

 #define OK 0

 typedef struct edgeNode{

     int data;

     int weight;

     struct edgeNode *next;

 }EdgeNode;

 typedef struct headNode{

     int in;

     int data;

     EdgeNode *fnode;

 }HeadNode,HeadList[MAX];

 typedef struct{

     HeadList headlist;

     int numEdges,numVertexes;

 }Graph,*graph;

 int *etv,*ltv;

 int *stack2;

 int top2;

 void initialGraph(Graph *g);

 void headinfo(Graph *g,int in,int node);

 void linkinfo(Graph *g,int node,int link,int weight);

 void printGraph(Graph *g);

 int topSort(Graph *g);

 int critical(Graph *g);

 int main(){

     Graph *g = (Graph *)malloc(sizeof(Graph));

     g->numEdges = ;

     g->numVertexes = ;

     initialGraph(g);

     printGraph(g);

     critical(g);

     //topSort(g);

     getchar();

     return ;

 }

 int critical(Graph *g){

     EdgeNode *e;

     int i,gettop,k,j;

     int ete,lte;

     topSort(g);

     printf("\n-------------------------------------------\n");

     for(i=;i<g->numVertexes;i++){

         printf("%d ",etv[i]);

     }

     printf("\n-------------------------------------------\n");

     ltv = (int *)malloc(sizeof(int)*g->numVertexes);

     for(i=;i<g->numVertexes;i++){

         ltv[i] = etv[g->numVertexes-];

     }

     while(top2!=){

         gettop = stack2[top2--];

         for(e = g->headlist[gettop].fnode;e;e = e->next){

             k = e->data;

             if(ltv[k]-e->weight < ltv[gettop]){

                 ltv[gettop] = ltv[k] - e->weight;

             }

         }

     }

     for(i=;i<g->numVertexes;i++){

         printf("%d ",ltv[i]);

     }

     printf("\n-------------------------------------------\n");

     printf("\n");

     for(j=;j<g->numVertexes;j++){

         for(e=g->headlist[j].fnode; e; e=e->next){

             k = e->data;

             ete = etv[j];//活动最早

             lte = ltv[k] - e->weight;//活动最迟

             if(ete == lte)

                 printf("<v%d v%d>length:%d\n",g->headlist[j].data,g->headlist[k].data,e->weight);

         }

     }

     return ;

 }

 int topSort(Graph *g){

     EdgeNode *e;

     int i,k,gettop;

     int top =  ;

     int count = ;

     int *stack;

     stack = (int *)malloc(g->numVertexes * sizeof(int));

     for(i=;i<g->numVertexes;i++){

         if(g->headlist[i].in == ) //把入度为0的，即没有入度的点入栈

             stack[++top] = i;

     }

     top2 = ;

     etv = (int *)malloc(g->numVertexes*sizeof(int));

     for(i=;i<g->numVertexes;i++){

         etv[i] = ;

     }

     stack2=(int *)malloc(g->numVertexes*sizeof(int));

     while(top){

         gettop = stack[top--];

         printf("%d ",gettop);

         count++;

         stack2[++top2] = gettop;

         for(e = g->headlist[gettop].fnode; e ; e=e->next){ //一次遍历链表，减少各个子节点的入度

             k = e->data;

             if(!(--g->headlist[k].in))

                 stack[++top] = k;

             if((etv[gettop]+e->weight)>etv[k]) //选取最大值

                 etv[k] = etv[gettop]+e->weight;

         }

     }

     if(count < g->numVertexes)

         return ERROR;

     else

         return OK;

 }

 void printGraph(graph g){

     int i;

     printf("vertex:%d,edges:%d\n",g->numVertexes,g->numEdges);

     EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));

     for(i=;i<MAX;i++){

         printf("[in:%d]%d",g->headlist[i].in,g->headlist[i].data);

         e = g->headlist[i].fnode;

         while(e != NULL){

             printf("->%d(%d)",e->data,e->weight);

             e = e->next;

         }

         printf("\n");

     }

     free(e);

 }

 void initialGraph(Graph *g){

     headinfo(g,,);

     linkinfo(g,,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     headinfo(g,,);

     linkinfo(g,,,);

     headinfo(g,,);

 }

 void headinfo(Graph *g,int in,int node){

     g->headlist[node].in = in;

     g->headlist[node].data = node;

     g->headlist[node].fnode = NULL;

     g->numVertexes++;

 }

 void linkinfo(Graph *g,int node,int link,int weight){

     EdgeNode *en = (EdgeNode *)malloc(sizeof(EdgeNode));

     if(g->headlist[node].fnode != NULL){

         en->next = g->headlist[node].fnode;

     }else{

         en->next = NULL;

     }

     g->headlist[node].fnode = en;

     en->data = link;

     en->weight = weight;

     g->numEdges++;

 }