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

2024-03-29 14:32
文章标签 分析 代码 解析 long 思路 pta take

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

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

  • 一、前导
    • 1. 需要掌握的知识
    • 2. 题目信息
  • 二、解题思路分析
    • 1. 题意理解
      • 1. 1 输入数据
      • 1.2 输出数据
    • 2. 思路分析（重点）
  • 三、具体实现
    • 1. 弯路和bug
    • 2. 代码框架（重点）
      • 2.1 采用的数据结构
      • 2.2 程序主体框架
      • 2.3 各分支函数
    • 3. 完整AC编码
  • 四、参考

一、前导

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;} 
}
  1. 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 思路分析及代码解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/858841。

相关文章

Java调用DeepSeek API的最佳实践及详细代码示例

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》：本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.
阅读更多...
Springboot中分析SQL性能的两种方式详解

Springboot中分析SQL性能的两种方式详解

《Springboot中分析SQL性能的两种方式详解》文章介绍了SQL性能分析的两种方式：MyBatis-Plus性能分析插件和p6spy框架,MyBatis-Plus插件配置简单,适用于开发和测试环... 目录SQL性能分析的两种方式:功能介绍实现方式:实现步骤:SQL性能分析的两种方式:功能介绍记录
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...
Python中顺序结构和循环结构示例代码

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
最长公共子序列问题的深度分析与Java实现方式

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列（LCS）问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动
阅读更多...
linux进程D状态的解决思路分享

linux进程D状态的解决思路分享

《linux进程D状态的解决思路分享》在Linux系统中,进程在内核模式下等待I/O完成时会进入不间断睡眠状态（D状态）,这种状态下,进程无法通过普通方式被杀死,本文通过实验模拟了这种状态,并分析了如... 目录1. 问题描述2. 问题分析3. 实验模拟3.1 使用losetup创建一个卷作为pv的磁盘3.
阅读更多...
MySQL数据库函数之JSON_EXTRACT示例代码

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》：本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意
阅读更多...
CSS3中使用flex和grid实现等高元素布局的示例代码

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》：本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法，通过简单的两列实现、每行放置3列以及全部代码的展示，展示了这两种布局方式的实现细节和效果，详细内容请阅读本文，希望能对你有所帮助... 过往的实现方法是使用浮动加
阅读更多...
JAVA调用Deepseek的api完成基本对话简单代码示例

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》：本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先，从DeepSeek平台获取API密钥，用于身份验证。添加HTTP客户端依赖使用Jav
阅读更多...
Java实现状态模式的示例代码

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2