PTA How Long Does It Take 思路分析及代码解析

本文主要是介绍PTA How Long Does It Take 思路分析及代码解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、前导

1. 需要掌握的知识

1. AOV网：顶点表示活动，边表示活动间先后关系的有向图 称做 顶点活动网络(Activity On Vertex network)，简称AOV网
2. 在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列 称为 拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做 拓扑排序(Topological sort)。
3. AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
4. AOV网构造出拓扑序列的实际意义：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。示例：某专业学生的排课
5. 拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止
   (1) 选择一个入度为0的顶点并输出
   (2) 从AOV网中删除此顶点及所有出边
   循环结束后，若输出的顶点数 < AOV网中的顶点数，则说明图中存在回路，不存在拓扑序列；若相等，输出的顶点序列就是一种拓扑序列

2. 题目信息

1. 题目来源：PTA / 拼题A
2. 题目地址：How Long Does It Take

二、解题思路分析

1. 题意理解

1. 拓扑排序相关问题

1. 1 输入数据

9 12  //图的顶点数和边数,顶点数最大值100,顶点从0开始编号
0 1 6 //边的两个顶点及其权重, 有向图 0-->1
0 2 4
...
7 8 4

1.2 输出数据

1. 打印最早完成时间；图如果存在回路，打印 ‘Impossible’

2. 思路分析（重点）

1. 拓扑排序相关问题：判断图中是否存在回路 + 计算出最早完成时间(不严谨的表述就是：边的权值之和的最大值)

三、具体实现

1. 弯路和bug

1. 使用指针变量时，先申请内存空间，然后再使用

ptrAdjNode N;
N=(ptrAdjNode)malloc(sizeof(struct AdjNodeStructure));

2. 代码框架（重点）

2.1 采用的数据结构

1. 使用邻接表存储图：图结构如下所示

typedef int vertex;
typedef int wightType;
#define max 100struct EdgeStruc  //边结构
{vertex V1;vertex V2;wightType weight;
};
typedef struct EdgeStruc *ptrEdge; typedef struct AdjNodeStructure *ptrAdjNode;
struct AdjNodeStructure //图顶点的邻接点
{vertex vertexIndex;wightType weight;ptrAdjNode next;
};struct HeadNode //邻接表的头结点
{ptrAdjNode AdjNode;
};
typedef struct HeadNode HeadNodeArray[max];struct GraphStructure //图
{int vertexNumber;int edgeNumber;HeadNodeArray head;
};
typedef struct GraphStructure *ptrGraph;

2.2 程序主体框架

               程序伪码描述
int main()
{	构建图 然后执行拓扑排序即可return 0;
}

2.3 各分支函数

1. TopSort( )：拓扑排序子函数。拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止
   (1) 选择一个入度为0的顶点并输出
   (2) 从AOV网中删除此顶点及所有出边
   循环结束后，若输出的顶点数 < AOV网中的顶点数，则说明图中存在回路，不存在拓扑序列；若相等，输出的顶点序列就是一种拓扑序列

int TopSort()
{int Indegree[Graph->vertexNumber],cnt=0,front,result=0;vertex V;ptrAdjNode W;queue<vertex> q;/* 初始化入度 */for(V=0;V<Graph->vertexNumber;V++)Indegree[V]=0;/*遍历图 得到Indegree[] */for(V=0;V<Graph->vertexNumber;V++){W=Graph->head[V].AdjNode;while(W){Indegree[W->vertexIndex]++;W=W->next;}		} /*将所有入度为0的顶点入列*/for(V=0;V<Graph->vertexNumber;V++) {if(Indegree[V]==0){q.push(V);Earlist[V]=0;}}/*开始进行Top Sort*/while(!q.empty()) {front=q.front();q.pop();cnt++;//TopOrder[cnt++]=front;W=Graph->head[front].AdjNode; while(W) {if(Earlist[W->vertexIndex]<Earlist[front] + W->weight) //计算最早完成时间 Earlist[W->vertexIndex]=Earlist[front]+W->weight; if(--Indegree[W->vertexIndex] == 0){q.push(W->vertexIndex);}	W=W->next;	} }if(cnt!=Graph->vertexNumber)return result;else {  // Earlist数组中的最大值就是最早完成时间for(V=0;V<Graph->vertexNumber;V++)  {if(Earlist[V]>result)result=Earlist[V];}return result;} 
}

3. BuildGraph( ) ：通过邻接表存储图，属于建图的基础练习

3. 完整AC编码

1. 本文如果对你有帮助，请点赞鼓励 ，谢谢 😊
2. 如有建议或意见，欢迎留言

#include <queue>
#include <cstdlib>
#include <iostream>
using namespace std;typedef int vertex;
typedef int wightType;
#define max 100struct EdgeStruc
{vertex V1;vertex V2;wightType weight;
};
typedef struct EdgeStruc *ptrEdge; typedef struct AdjNodeStructure *ptrAdjNode;
struct AdjNodeStructure
{vertex vertexIndex;wightType weight;ptrAdjNode next;
};struct HeadNode
{ptrAdjNode AdjNode;
};
typedef struct HeadNode HeadNodeArray[max];struct GraphStructure
{int vertexNumber;int edgeNumber;HeadNodeArray head;
};
typedef struct GraphStructure *ptrGraph;ptrGraph Graph;
int Earlist[max]={0}; //统计最早完成时间 
//vertex TopOrder[max]; //存放拓扑排序的结果void CreateNullNodeGraph();
void BuildGraph();
void insertEdge(ptrEdge Edge);
int TopSort();int main()
{	int result;BuildGraph();result=TopSort();if(!result)cout<<"Impossible";elsecout<<result;return 0;
} int TopSort()
{int Indegree[Graph->vertexNumber],cnt=0,front,result=0;vertex V;ptrAdjNode W;queue<vertex> q;/* 初始化入度 */for(V=0;V<Graph->vertexNumber;V++)Indegree[V]=0;/*遍历图 得到Indegree[] */for(V=0;V<Graph->vertexNumber;V++){W=Graph->head[V].AdjNode;while(W){Indegree[W->vertexIndex]++;W=W->next;}		} /*将所有入度为0的顶点入列*/for(V=0;V<Graph->vertexNumber;V++) {if(Indegree[V]==0){q.push(V);Earlist[V]=0;}}/*开始进行Top Sort*/while(!q.empty()) {front=q.front();q.pop();cnt++;//TopOrder[cnt++]=front;W=Graph->head[front].AdjNode; while(W) {if(Earlist[W->vertexIndex]<Earlist[front] + W->weight) //计算最早完成时间 Earlist[W->vertexIndex]=Earlist[front]+W->weight; if(--Indegree[W->vertexIndex] == 0){q.push(W->vertexIndex);}	W=W->next;	} }if(cnt!=Graph->vertexNumber)return result;else {  // Earlist数组中的最大值就是最早完成时间for(V=0;V<Graph->vertexNumber;V++)  {if(Earlist[V]>result)result=Earlist[V];}return result;} 
}void CreateNullNodeGraph()
{Graph=(ptrGraph)malloc(sizeof(struct GraphStructure));cin>>Graph->vertexNumber>>Graph->edgeNumber;for(int i=0;i<Graph->vertexNumber;i++){Graph->head[i].AdjNode=NULL;}
}void BuildGraph()
{ptrEdge Edge;  CreateNullNodeGraph();for(int i=0;i<Graph->edgeNumber;i++){Edge=(ptrEdge)malloc(sizeof(struct EdgeStruc));cin>>Edge->V1>>Edge->V2>>Edge->weight;insertEdge(Edge);	}return;
}void insertEdge(ptrEdge Edge)
{ptrAdjNode N;N=(ptrAdjNode)malloc(sizeof(struct AdjNodeStructure));N->vertexIndex=Edge->V2;N->weight=Edge->weight;N->next=Graph->head[Edge->V1].AdjNode;Graph->head[Edge->V1].AdjNode=N;return;
}

四、参考

1. 浙江大学 陈越、何钦铭老师主讲的数据结构

这篇关于PTA How Long Does It Take 思路分析及代码解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---