10.7

总结下今天早上的东西。

1,从加边开始。哈哈。其实之前是跟着敲了代码的,但是我觉得可能是没有回顾吧,然后就挺差的。

2,加边中的const不会了,但是一本通上面是有的。

3,还有动态数组是一维的还是二维的?

从循环上来看可能是一维的。

4,理解到位靠的是啥呢?靠的是手动模拟(滑稽),所以说面对不懂的代码,手动模拟先!!毕竟也是之前的经验。

5,第一个弄懂的是啥来着?

是根据HDU4707,这题主要是明白了一点深搜。代码在文件夹4707那里。

6,接下来是树的重心,

    (1)什么是树的重心

选定一个根节点后,剩下的子树的大小都相对接近。

同时树的重心还有几个性质,除了第一个好像也不是很重要。但是怎么求树的重心

,则借鉴了树的定义和树的第一个性质,

那么我们怎么求一个树的重心呢?

核心思想是找出,以各个点为根节点时,各个点对应的最大子树中的最小值。

懂了一点,但不完全。

    (2)有什么用呢?

说是用于树的分治算法,但是也没讲到。

7,树的直径,

    有边权的情况下,最长的一条树链。(一般包括着根节点)

同时还给出了一个定理,就是任意一点离他最远的点必然在直径的端点上。

   (1)怎么求。。

说是用dfs一遍,但是...也没有仔细讲,就2:26有点代码。

8,图。

    (1)什么是图

本质上是一种多对多关系的具体化,(树就是一种特殊的图)

同时从图的起源,戈尼斯堡七桥问题,欧拉的第一步研究方法,建模思想以及其后的思想很值得学习。

①存在着有向无向的概念。

有向又会引申出自环的概念。

但是无向不会存在自环。

②存在着入度和出度的概念。

③存在着联通不连通的概念

同时联通图又可以引申出强连通图这个概念。

    (2)

用什么来存图。。

联系下树。。没错我们用vetor。

9,区分一下树和图

①树一定是无向的;

②树一定是联通的;

③树的边数一定是树的节点数-1;

④树不会成环;

原文地址:https://www.cnblogs.com/beiyueya/p/11629753.html