Posted on Edited on

写在前面

这里用来记录PAT解题的一些考点,注意事项,源代码请到这里[link]去找. 按照题号写的, “XX_w2.cpp”是参考的大神的代码

2020.5.16

1106 Lowest Price in Supply Chain

同类题目:

  • 求叶子结点的最小层
  • 有向无权图的单元最短路的条数

​ 考点: 利用 图的DFS / BFS 求叶子结点的最小层(要减枝,不然会超时)

利用vector<int> Nodes[max] 构建邻接链表

问题

  1. 结果要求保留小数点后4位, 需要控制输出格式 , cout<<setiosflag(ios::fixed)<<setprecision(4)<<…
  2. 一般用double代替float,保留一定的精度
  3. 边界min_depth的初值我设置成9999, 有点小,卡了三个样例,要注意边界值的设置
  4. bfs,我经常容易忘记结点出队/=,害

1115 Counting Nodes in a BST

  • 计算BST中最低层和次低层的结点的个数

相关考点:

1. BST的构建--insert,creatBST模板函数
 2. DFS

问题:

​ 这次还是边界设置错啦,–int depth=-1; //只有一个结点的时候,出错

1114 Family Property

  • 统计求集合的并集,并集合中的信息

相关考点:

​ 1.并查集的find 和 union 模板(==遗留问题, 路径压缩的并查集和非路径压缩有什么区别??,这里带路径压缩的find会导致出错)

  1. 这里的4位的id是直接用int来表示的,方便并查集的实现;不过最后的输出格式要额外处理

    • 如何把int转换成string,并且高位用0填充
      • char des[10] ; int src = 1998 ;
      • sprintf(des,”%04d”,src); //把src转换为4位的string,并用0填充,转换的结果存储到des中.

  2. 经常开一个比较大的数组作为全局变量.节省一些处理.

    这道题开大数组,索引起来特别方便.不过要增加一个vis[10000]数组表示id是有效的.

    (自己做题总是小心翼翼,不想浪费太多的空间)

  3. 这道题数据处理的过程,可以多学习一些,自定义了两个struct,一个用来处理输入(输入一个结点,进行一次union操作,int father[]用来保存并查集结构) ；另外一个用来处理输出,(保存每个集合的统计信息)

1126 Eulerian Path

  • 判断图是否是欧拉图,半欧拉图,非欧拉图

    • 欧拉图的定义

      欧拉回路：图G中经过每条边一次并且仅一次的回路称作欧拉回路

      欧拉通路：图G中经过每条边一次并且仅一次的路径称作欧拉通路。
      欧拉图(Eulerian graph)指的就是存在欧拉回路的图。
      半欧拉图(semi-Eulerian graph)指的是存在欧拉通路但不存在欧拉回路的图。

      1.无向图中：

      无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。

      　无向图G为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。

      2.有向图中：
      　　有向图G为欧拉图，当且仅当G为连通图，且所有顶点的入度等于出度。
      　　有向图G为半欧拉图，当且仅当G为连通图，且存在顶点u的入度比出度大1，v的入度比出度小1，其它所有顶点的入度等于出度。

基本思路:

  1. 统计所有顶点的度,计算度为奇数的结点的个数
  2. 判断该图是否是连通图

考点

​ 如何判断是否是连通图?

​ 1.利用并查集(在接收输入时,构建并查集) ,时间复杂度

​ 2. 一次深搜DFS ,时间复杂度: