08-图8 How Long Does It Take(C)

哈哈，很明显这是一个有向无环图，用邻接表更好一些 ，

这一个考察的是拓扑排序的简单应用。

测试点	提示	内存(KB)	用时(ms)	结果	得分
0	sample 1 一般情况，有0边，单个起点和单个终点	192	4	答案正确	15 / 15
1	sample 2 有环	316	5	答案正确	2 / 2
2	多个起点和多个终点	320	4	答案正确	4 / 4
3	最大N，不可行	320	4	答案正确	2 / 2
4	最大N，可行	316	4	答案正确	2 / 2

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1), and M, the number of activities. Then M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.

Output Specification:

For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output "Impossible".

Sample Input 1:

9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

Sample Output 1:

18

Sample Input 2:

4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

Sample Output 2:

Impossible

 我的AC:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>typedef struct ENode *Edge;
struct ENode{int V1, V2;int Weight;
};typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{int V;int Weight;PtrToAdjVNode Next;
};typedef struct VNode *AdjList;
struct VNode{PtrToAdjVNode FirstEdge;
};typedef struct GNode *LGraph;
struct GNode{int Nv;int Ne;AdjList	*G;
};typedef struct Node *QNode;
struct Node{int data;QNode Next;
};typedef struct QNode *Queue;
struct QNode{QNode Front;QNode Rear;
};void Build_Graph(LGraph M, int *InDegree);
LGraph Init_Graph();
void Insert_Graph(LGraph M, Edge E);
Queue Init_Queue();
void Add_Q(Queue Q, int data);
int Delete_Q(Queue Q);
bool IsEmpty_Q(Queue Q);
bool TopSort(LGraph M, int *InDegree, int *EarthTime);
int Max_time(int *EarthTime, int N);int main()
{LGraph M;int *InDegree;int *EarthTime;M = Init_Graph();	EarthTime = (int*)calloc(M ->Nv, sizeof(int));InDegree = (int*)calloc(M ->Nv, sizeof(int));Build_Graph(M, InDegree);if(TopSort(M, InDegree, EarthTime)){printf("%d\n", Max_time(EarthTime, M ->Nv));}else{printf("Impossible\n");}return 0;
}
bool TopSort(LGraph M, int *InDegree, int *EarthTime)
{PtrToAdjVNode G;Queue Q;int V = 0;int num = 0;Q = Init_Queue();for(V = 0; V < M ->Nv; V++){if(!InDegree[V]){Add_Q(Q, V);}}while(!IsEmpty_Q(Q)){V = Delete_Q(Q);num++;for(G = M ->G[V] ->FirstEdge; G; G = G ->Next){if(--InDegree[G ->V] == 0){Add_Q(Q, G ->V);}if(EarthTime[G ->V] < EarthTime[V] + G ->Weight){EarthTime[G ->V] = EarthTime[V] + G ->Weight;
//				printf("EarthTime[%d] = %d (%d ->%d)\n", G ->V, EarthTime[G ->V], G ->V, G ->V);}}	}if(num != M ->Nv){return false;}else{return true;}
}
int Max_time(int *EarthTime, int N)
{int time = 0;for(int i = 0; i < N; i++){if(EarthTime[i] > time){time = EarthTime[i];}}return time;
}
void Build_Graph(LGraph M, int *InDegree)
{Edge E;int i;E = (Edge)malloc(sizeof(struct ENode));for(i = 0; i < M ->Ne; i++){scanf("%d %d %d", &E ->V1, &E ->V2, &E ->Weight);Insert_Graph(M, E);InDegree[E ->V2]++;}
}
LGraph Init_Graph()
{LGraph M;M = (LGraph)malloc(sizeof(struct GNode));scanf("%d %d", &M ->Nv, &M ->Ne);M ->G = (AdjList*)malloc(sizeof(AdjList) * M ->Nv);for(int i = 0; i < M ->Nv; i++){M ->G[i] = (AdjList)malloc(sizeof(struct VNode));M ->G[i] ->FirstEdge= NULL;}return M;
}
void Insert_Graph(LGraph M, Edge E)
{PtrToAdjVNode NewNode;NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode ->V = E ->V2;NewNode ->Weight = E ->Weight;NewNode ->Next = M ->G[E ->V1] ->FirstEdge;M ->G[E ->V1] ->FirstEdge = NewNode;}
Queue Init_Queue()
{Queue Q;Q = (Queue)malloc(sizeof(struct QNode));Q ->Front = NULL;Q ->Rear  = NULL;return Q;
}
void Add_Q(Queue Q, int Vertex)
{QNode Node;Node = (QNode)malloc(sizeof(struct Node));Node ->data = Vertex;Node->Next = NULL;if(!(Q ->Front) && !(Q ->Rear)){Q ->Front = Node;Q ->Rear = Node;}else{Q ->Rear ->Next = Node;Q ->Rear = Node;}
}
int Delete_Q(Queue Q)
{if(IsEmpty_Q(Q)){printf("很遗憾，是空的！\n");return -1;}else{QNode Temp;int Vertex;Temp = Q ->Front;Q ->Front = Temp ->Next;Vertex = Temp ->data;if(IsEmpty_Q(Q)){Q ->Rear = NULL;}else{free(Temp);}return Vertex;}
}
bool IsEmpty_Q(Queue Q)
{return (Q ->Front == NULL);
}