全部每周作业和视频思考题答案和解析 见浙江大学 数据结构 思考题+每周练习答案
题目：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(≤100), 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.
每个输入文件包含一个测试用例。每种情况都以一行开始，该行包含两个正整数N（≤100）、活动检查点的数量（因此，假设检查点的编号范围为0到N-1）和M，即活动数量。接下来是M行，每行给出一个活动的描述。对于第i个活动，给出了三个非负数：S[i]，E[i]和L[i]，其中S[i]是开始检查点的索引，E[i]是结束检查点，L[i]是活动的持续时间。一行中的数字用空格隔开。
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 4
Sample Output 1:
18
Sample Input 2:
4 50 1 10 2 22 1 31 3 43 2 5
Sample Output 2:
Impossible
解答：
思路很简单，构成一个拓扑排序，把每层最多需要的时间记录，逐层记录。
这里需要注意，我们的拓扑结构是最简单的任务，不需要保证某些步骤同步进行，视频里说了一种复杂的情况，与该题无关，我之前就混淆了。
我们先整理一个使用邻接表存储的拓扑排序程序：
注意因为是有向图，所以插入边的操作需要去掉后半部分。题目给的顶点序号是0到N-1，所以不需要读入数据再减一（参考上个题，顶点序号1-N，所以需要进一步处理）。
#include <iostream>#include <queue>using namespace std;#define MaxVertexNum 1000typedef int Vertex;// 邻接表存储 - Kruskal最小生成树算法 //-------------------- 顶点并查集定义 --------------------typedef Vertex ElementType; // 默认元素可以用非负整数表示 typedef Vertex SetName;// 默认用根结点的下标作为集合名称 typedef ElementType SetType[MaxVertexNum]; // 假设集合元素下标从0开始typedef int WeightType; // 边的权值设为整型 typedef char DataType; // 顶点存储的数据类型设为字符型 queue<Vertex> myQueue;// 边的定义typedef struct ENode *PtrToENode;struct ENode {Vertex V1, V2;// 有向边<V1, V2> WeightType Weight; // 权重 };typedef PtrToENode Edge;//邻接点的定义 typedef struct AdjVNode *PtrToAdjVNode;struct AdjVNode {Vertex AdjV; // 邻接点下标 WeightType Weight; // 边权重 PtrToAdjVNode Next; // 指向下一个邻接点的指针 };//顶点表头结点的定义typedef struct Vnode {PtrToAdjVNode FirstEdge;// 边表头指针 DataType Data;// 存顶点的数据 // 注意：很多情况下，顶点无数据，此时Data可以不用出现 } AdjList[MaxVertexNum];// AdjList是邻接表类型 //图结点的定义 typedef struct GNode *PtrToGNode;struct GNode {int Nv;// 顶点数 int Ne;// 边数 AdjList G;// 邻接表 };typedef PtrToGNode LGraph; // 以邻接表方式存储的图类型 LGraph CreateGraph(int VertexNum){ //初始化一个有VertexNum个顶点但没有边的图 Vertex V;LGraph Graph;Graph = (LGraph)malloc(sizeof(struct GNode)); // 建立图 Graph->Nv = VertexNum;Graph->Ne = 0;//初始化邻接表头指针 //注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) for (V = 0; V<Graph->Nv; V++)Graph->G[V].FirstEdge = NULL;return Graph;}void InsertEdge(LGraph Graph, Edge E){PtrToAdjVNode NewNode;//插入边 <V1, V2> //为V2建立新的邻接点 NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V2;NewNode->Weight = E->Weight;//将V2插入V1的表头 NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;//注意拓扑排序是用的有向图//若是无向图，还要插入边 <V2, V1> //为V1建立新的邻接点 //NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));//NewNode->AdjV = E->V1;//NewNode->Weight = E->Weight;//将V1插入V2的表头 //NewNode->Next = Graph->G[E->V2].FirstEdge;//Graph->G[E->V2].FirstEdge = NewNode;}LGraph BuildGraph(){LGraph Graph;Edge E;Vertex V;int Nv, i;cin >> Nv; //读入顶点个数 Graph = CreateGraph(Nv); //初始化有Nv个顶点但没有边的图 cin >> Graph->Ne; //读入边数 if (Graph->Ne != 0) { //如果有边 E = (Edge)malloc(sizeof(struct ENode)); //建立边结点 //读入边，格式为"起点 终点 权重"，插入邻接矩阵 for (i = 0; i<Graph->Ne; i++) {cin >> E->V1 >> E->V2 >> E->Weight;//E->V1--;//E->V2--;//注意：如果权重不是整型，Weight的读入格式要改 InsertEdge(Graph, E);}}//如果顶点有数据的话，读入数据 //for (V = 0; V<Graph->Nv; V++)//cin >> Graph->G[V].Data;return Graph;}//邻接表存储 - 拓扑排序算法 bool TopSort(LGraph Graph, Vertex TopOrder[]){ //对Graph进行拓扑排序, TopOrder[]顺序存储排序后的顶点下标 int Indegree[MaxVertexNum], cnt;Vertex V;PtrToAdjVNode W;//初始化Indegree[] for (V = 0; V<Graph->Nv; V++)Indegree[V] = 0;//遍历图，得到Indegree[] for (V = 0; V<Graph->Nv; V++)for (W = Graph->G[V].FirstEdge; W; W = W->Next)Indegree[W->AdjV]++; //对有向边<V, W->AdjV>累计终点的入度 //将所有入度为0的顶点入列 for (V = 0; V < Graph->Nv; V++)if (Indegree[V] == 0)myQueue.push(V);//下面进入拓扑排序 cnt = 0;while (!myQueue.empty()) {V = myQueue.front(); //弹出一个入度为0的顶点 myQueue.pop();TopOrder[cnt++] = V; //将之存为结果序列的下一个元素 //对V的每个邻接点W->AdjV for (W = Graph->G[V].FirstEdge; W; W = W->Next)if (--Indegree[W->AdjV] == 0)//若删除V使得W->AdjV入度为0 myQueue.push(W->AdjV); //则该顶点入列 } //while结束if (cnt != Graph->Nv)return false; //说明图中有回路, 返回不成功标志 elsereturn true;}int main(void) {LGraph myGraph = BuildGraph();Vertex TopOrder[MaxVertexNum];bool flag = TopSort(myGraph, TopOrder);if (true == flag) {for (int i = 0;i < myGraph->Nv;i++) {cout << TopOrder[i] << " ";}cout << endl;}else {cout << " 有回路 " << endl;}cout << endl;system("pause");return 0;}
打印输出结果为：0 3 2 1 5 4 7 6 8
说明我们的拓扑排序程序是正确的。
然后我们只需要在每个点到其连接点的判断中加入一句话：
if ((Earliest[V] + W->Weight)>Earliest[W->AdjV]) {Earliest[W->AdjV] = Earliest[V] + W->Weight;}
也就是说找到每一组到后面最大的数。
然后最后别忘了要找到Earliest数组里面最大的数，因为最大的数才是总项目最短完成时间。
全部代码如下：
#include <iostream>#include <queue>using namespace std;#define MaxVertexNum 1000typedef int Vertex;// 邻接表存储 - Kruskal最小生成树算法 //-------------------- 顶点并查集定义 --------------------typedef Vertex ElementType; // 默认元素可以用非负整数表示 typedef Vertex SetName;// 默认用根结点的下标作为集合名称 typedef ElementType SetType[MaxVertexNum]; // 假设集合元素下标从0开始typedef int WeightType; // 边的权值设为整型 typedef char DataType; // 顶点存储的数据类型设为字符型 Vertex Earliest[MaxVertexNum];queue<Vertex> myQueue;// 边的定义typedef struct ENode *PtrToENode;struct ENode {Vertex V1, V2;// 有向边<V1, V2> WeightType Weight; // 权重 };typedef PtrToENode Edge;//邻接点的定义 typedef struct AdjVNode *PtrToAdjVNode;struct AdjVNode {Vertex AdjV; // 邻接点下标 WeightType Weight; // 边权重 PtrToAdjVNode Next; // 指向下一个邻接点的指针 };//顶点表头结点的定义typedef struct Vnode {PtrToAdjVNode FirstEdge;// 边表头指针 DataType Data;// 存顶点的数据 // 注意：很多情况下，顶点无数据，此时Data可以不用出现 } AdjList[MaxVertexNum];// AdjList是邻接表类型 //图结点的定义 typedef struct GNode *PtrToGNode;struct GNode {int Nv;// 顶点数 int Ne;// 边数 AdjList G;// 邻接表 };typedef PtrToGNode LGraph; // 以邻接表方式存储的图类型 LGraph CreateGraph(int VertexNum){ //初始化一个有VertexNum个顶点但没有边的图 Vertex V;LGraph Graph;Graph = (LGraph)malloc(sizeof(struct GNode)); // 建立图 Graph->Nv = VertexNum;Graph->Ne = 0;//初始化邻接表头指针 //注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) for (V = 0; V<Graph->Nv; V++)Graph->G[V].FirstEdge = NULL;return Graph;}void InsertEdge(LGraph Graph, Edge E){PtrToAdjVNode NewNode;//插入边 <V1, V2> //为V2建立新的邻接点 NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->AdjV = E->V2;NewNode->Weight = E->Weight;//将V2插入V1的表头 NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;//注意拓扑排序是用的有向图//若是无向图，还要插入边 <V2, V1> //为V1建立新的邻接点 //NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));//NewNode->AdjV = E->V1;//NewNode->Weight = E->Weight;//将V1插入V2的表头 //NewNode->Next = Graph->G[E->V2].FirstEdge;//Graph->G[E->V2].FirstEdge = NewNode;}LGraph BuildGraph(){LGraph Graph;Edge E;Vertex V;int Nv, i;cin >> Nv; //读入顶点个数 Graph = CreateGraph(Nv); //初始化有Nv个顶点但没有边的图 cin >> Graph->Ne; //读入边数 if (Graph->Ne != 0) { //如果有边 E = (Edge)malloc(sizeof(struct ENode)); //建立边结点 //读入边，格式为"起点 终点 权重"，插入邻接矩阵 for (i = 0; i<Graph->Ne; i++) {cin >> E->V1 >> E->V2 >> E->Weight;//E->V1--;//E->V2--;//注意：如果权重不是整型，Weight的读入格式要改 InsertEdge(Graph, E);}}//如果顶点有数据的话，读入数据 //for (V = 0; V<Graph->Nv; V++)//cin >> Graph->G[V].Data;return Graph;}//返回最大的元素Vertex getMaxElement(Vertex arr[],int N) {Vertex maxElement = 0;for (int i = 0; i < N; i++)if (maxElement < arr[i])maxElement = arr[i];return maxElement;}//邻接表存储 - 拓扑排序算法 bool TopSort(LGraph Graph, Vertex TopOrder[]){ //对Graph进行拓扑排序, TopOrder[]顺序存储排序后的顶点下标 int Indegree[MaxVertexNum], cnt;Vertex V;PtrToAdjVNode W;//初始化Indegree[] for (V = 0; V<Graph->Nv; V++)Indegree[V] = 0;//遍历图，得到Indegree[] for (V = 0; V<Graph->Nv; V++)for (W = Graph->G[V].FirstEdge; W; W = W->Next)Indegree[W->AdjV]++; //对有向边<V, W->AdjV>累计终点的入度 //将所有入度为0的顶点入列 for (V = 0; V < Graph->Nv; V++)if (Indegree[V] == 0)myQueue.push(V);//下面进入拓扑排序 cnt = 0;while (!myQueue.empty()) {V = myQueue.front(); //弹出一个入度为0的顶点 myQueue.pop();TopOrder[cnt++] = V; //将之存为结果序列的下一个元素 //对V的每个邻接点W->AdjV for (W = Graph->G[V].FirstEdge; W; W = W->Next) {if (--Indegree[W->AdjV] == 0)//若删除V使得W->AdjV入度为0 myQueue.push(W->AdjV); //则该顶点入列 if ((Earliest[V] + W->Weight)>Earliest[W->AdjV]) {Earliest[W->AdjV] = Earliest[V] + W->Weight;}}} //while结束if (cnt != Graph->Nv)return false; //说明图中有回路, 返回不成功标志 elsereturn true;}int main(void) {LGraph myGraph = BuildGraph();Vertex TopOrder[MaxVertexNum];bool flag = TopSort(myGraph, TopOrder);Vertex showestTime = getMaxElement(Earliest, myGraph->Nv);if (true == flag) {cout << showestTime;}else {cout << "Impossible";}system("pause");return 0;}
测试结果：
如果觉得《算法 图8 How Long Does It Take》对你有帮助，请点赞、收藏，并留下你的观点哦！
