一、题目
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 integersN(≤), the number of activity check points (hence it is assumed that the check points are numbered from 0 toN−1), andM, the number of activities. ThenMlines follow, each gives the description of an activity. For thei-th activity, three non-negative numbers are given:S[i],E[i], andL[i], whereS[i]is the index of the starting check point,E[i]of the ending check point, andL[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 120 1 60 2 40 3 51 4 12 4 13 5 25 4 04 6 94 7 75 7 46 8 27 8 4Sample Output 1:18Sample Input 2:4 50 1 10 2 22 1 31 3 43 2 5Sample Output 2:Impossible
二、思路
规规矩矩的拓扑排序
三、参考代码
#include <stdlib.h> #include <cstdio>#include <queue>#define MaxVertexNum 102#define INFINITY 65536using namespace std;typedef int Vertex; typedef int WeightType; typedef int DataType; int Indegree[MaxVertexNum];typedef struct ENode *Edge;struct ENode{Vertex V1, V2;WeightType Weight; };typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{Vertex AdjV; WeightType Weight; PtrToAdjVNode Next; };typedef struct Vnode{PtrToAdjVNode FirstEdge;DataType Data; } AdjList[MaxVertexNum]; /* AdjListÊÇÁÚ½Ó±íÀàÐÍ */typedef struct GNode *LGraph;struct GNode{ int Nv;int Ne;AdjList G; };LGraph CreateGraph( int VertexNum );void InsertEdge( LGraph Graph, Edge E );LGraph BuildGraph();bool topSort(LGraph Graph);void find_max(LGraph Graph);int main() {LGraph Graph = BuildGraph();if( !topSort(Graph) ) printf("Impossible\n");else {find_max(Graph);}}LGraph CreateGraph( int VertexNum ){ Vertex V;LGraph Graph;Graph = (LGraph)malloc( sizeof(struct GNode) ); Graph->Nv = VertexNum;Graph->Ne = 0;for (V=0; V<Graph->Nv; V++)Graph->G[V].FirstEdge = NULL;return Graph; }void InsertEdge( LGraph Graph, Edge E ){PtrToAdjVNode newNode = new AdjVNode;newNode->Weight = E->Weight;newNode->AdjV = E->V2;newNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = newNode;}LGraph BuildGraph(){LGraph Graph;int Nv;Edge E;Vertex V;scanf("%d", &Nv);Graph = CreateGraph(Nv);scanf("%d", &(Graph->Ne));if(Graph->Ne) {E = new ENode;for(int i=0; i<Graph->Ne; i++) {scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight));InsertEdge(Graph, E);} }for(V=0; V<Graph->Nv; V++) {Graph->G[V].Data = 0;}return Graph;}bool topSort(LGraph Graph) {int cnt;Vertex V;queue<Vertex> Q;cnt = 0;for( V=0; V<Graph->Nv; V++) Indegree[V] = 0;for( V = 0; V < Graph->Nv; V++) {for(PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W=W->Next) {Indegree[W->AdjV]++;Graph->G[W->AdjV].Data = 0;}}for(V=0; V<Graph->Nv; V++) if(Indegree[V] == 0) Q.push(V);while(!Q.empty()) {V = Q.front();Q.pop();cnt++;for(PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W=W->Next) {if(--Indegree[W->AdjV] == 0) Q.push(W->AdjV);if(Graph->G[W->AdjV].Data < W->Weight + Graph->G[V].Data) Graph->G[W->AdjV].Data = W->Weight + Graph->G[V].Data;}}if(cnt != Graph->Nv) return false;return true;}void find_max(LGraph Graph){Vertex V;int compTime;compTime = Graph->G[0].Data;for(V = 1; V < Graph->Nv; V++) {if(Graph->G[V].Data > compTime) compTime = Graph->G[V].Data;}printf("%d\n", compTime);}
View Code
如果觉得《08-图8 How Long Does It Take》对你有帮助，请点赞、收藏，并留下你的观点哦！
