八、图(下)：How Long Does It Take

本文主要是介绍八、图(下)：How Long Does It Take，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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:

Sample Output 1:
18
Sample Input 2:

Sample Output 2:

Impossible

代码

#include<stdio.h>
#include<stdbool.h>
#include<malloc.h> 
#define MaxCheckNum 100
typedef int CheckPoint;
typedef int WeightType;
int Indegree[MaxCheckNum] = {0}; /* 入度数组，初始化为0 */
int Day[MaxCheckNum] = {0};
CheckPoint TopOrder[MaxCheckNum];typedef struct ENode *Edge;
struct ENode{CheckPoint P1;CheckPoint P2;WeightType Weight;
};typedef struct AdjNode *PtrToAdjNode;
struct AdjNode{CheckPoint P;PtrToAdjNode Next;WeightType Weight;
};typedef struct HNode{PtrToAdjNode FirstEdge;
}Head[MaxCheckNum];typedef struct LNode *LGraph;
struct LNode{int Nv;int Ne;Head G;
};LGraph CreateGraph(int N)
{CheckPoint i;LGraph Graph = (LGraph)malloc(sizeof(struct LNode));Graph->Nv = N;Graph->Ne = 0;for(i=0; i!=N; ++i){Graph->G[i].FirstEdge = NULL;}return Graph;
}void InsertEdge(LGraph Graph, Edge E)
{PtrToAdjNode Adj = (PtrToAdjNode)malloc(sizeof(struct AdjNode));Adj->P = E->P2;Adj->Next = Graph->G[E->P1].FirstEdge;Adj->Weight = E->Weight;Graph->G[E->P1].FirstEdge = Adj;++Indegree[E->P2];/* 入度增加 */
}LGraph BuildGraph()
{int Nv, i;scanf("%d",&Nv);LGraph Graph = CreateGraph(Nv);scanf("%d",&Graph->Ne);Edge E = (Edge)malloc(sizeof(struct ENode));for(i=0; i!=Graph->Ne; ++i){scanf("\n%d %d %d",&E->P1,&E->P2,&E->Weight);InsertEdge(Graph, E);}return Graph;
}/* 实现队列 */
CheckPoint Que[MaxCheckNum] = {0};
int first = 0;
int last = -1;bool TopSort(LGraph Graph)
{CheckPoint i;int cnt;PtrToAdjNode W;for(i=0; i!=Graph->Nv; ++i){/* 查找入度为0的检查点，入队列 */if(Indegree[i] == 0)Que[++last] = i;}cnt = 0;while(first<=last){/* 队列不为空 */i = Que[first++];/* 弹出一个入度为0的顶点 */TopOrder[cnt++] = i;/* 存为结果序列的下一个元素 */for(W=Graph->G[i].FirstEdge; W!=NULL; W=W->Next){if(W->Weight+Day[i]>Day[W->P]) /* 更新到达W->P检查点的最小时间 */Day[W->P] = W->Weight+Day[i];if(--Indegree[W->P]==0)Que[++last] = W->P;}}if(cnt != Graph->Nv )return false;elsereturn true;
}int main()
{LGraph Graph = BuildGraph();if(TopSort(Graph)){int i = 0,max = 0;for(i=0;i!=Graph->Nv;++i)if(Day[i]>max)max = Day[i];printf("%d",max);}elseprintf("Impossible");
}

解题思路

拓扑排序：
1.用邻接表的方式建图。
2.建立入度数组，通过图可以获得每个结点的入度。
3.入度为0的结点进入一个队列。
4.结点出队列，进入排序数组。出队列的结点的邻接点入度都减1.如果减1后入度变成0了，就把这个邻接点入队列。
计算时间：
增加一个数组Day[ ],储存每个结点的日期，初始都为0。在拓扑排序的第4步，如果出队列的结点的日期Day[i]，加上到邻接点的需要耗费的时间W->Weight,大于邻接点原来的日期Day[W->P],就更新邻接点的日期。
最后遍历Day[ ]数组，输出其中的最大值。

这篇关于八、图(下)：How Long Does It Take的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！