10 5普及组2018洛谷秋令营普及组已下图论-PJ

1、图论-普及,洛谷 - icy 2018-2,洛谷网校冬令营 2018.2,Page 1,引子,冒泡排序，选择排序，插入排序，快速排序，堆排序，归并排序，希尔排序，桶排序，基数排序新年帮您排忧解难。 有向图，无向图，有环图，无环图，完全图，稠密图，稀疏图，拓扑图祝您新年宏图大展。 最长路，最短路，单源路径，所有节点对路径祝您新年路路通畅。 二叉树，红黑树，van Emde Boas树，最小生成树祝您新年好运枝繁叶茂。 最大流，网络流，标准输入流，标准输出流，文件输入流，文件输出流祝您新年顺顺流流。 线性动规，区间动规，坐标动规，背包动规，树型动归为您的新年规划精彩。 散列表，哈希表，邻接表，双向

2、链表，循环链表帮您在新年表达喜悦。 O(1), O(log n), O(n), O(nlog n), O(n2), O(n3), O(2n), O(n!)祝您新年渐进步步高。,洛谷网校冬令营 2018.2,Page 2,图论目录for普及,图是什么 图论简介 图的存储 图的存储与遍历 邻接矩阵 邻接表 图的遍历 图的最短路径 BFS灌水法 Floyd算法 Dijkstra算法 Spfa算法 图的最小生成树(MST) Prim算法 Kluskal算法 简单联通块及 拓扑排序和DAG 树 树的相关知识 树上节点最近公共祖先（LCA）,洛谷网校冬令营 2018.2,Page 3,图论目录for全体o

3、ier,图是什么 图论简介 图的存储 图的存储与遍历 邻接矩阵 邻接表 图的遍历 图的最短路径 BFS灌水法 Floyd算法 Dijkstra算法 Spfa算法 Bellman-ford算法 *Johnson算法 *A-Star算法 图的最小生成树(MST) Prim算法 Kluskal算法 *联通块及Tarjan强连通 树 树的相关知识 *最近公共祖先lca 树的直径 *树链剖分 *差分约束 *二分图匹配 *二叉树二叉堆 ,洛谷网校冬令营 2018.2,Page 4,图,下面的就是一张图（雾） 图片出自国产动漫镇魂街 这个只能算得上图片，不是图，不属于oi图论范围。,洛谷网校冬令营 2018

4、.2,Page 5,图,图论Graph Theory是数学的一个分支。它以图为研究对象，研究顶点和边组成的图形的数学理论和方法 。 图论发展到我们现在，已经拥有一个很庞大的体系。图论成为了信息学的一大专题，也出现过很多的难题。 如今我们学习图论要从最基础的开始学起，一步一步吃透图论，在将来的信息学竞赛拿分。 这才是真正oi中的图。 如你所见，图由点（我们放大为 圆圈）和线组成（或者带箭头的 线段）。,洛谷网校冬令营 2018.2,Page 6,图的相关定义术语,有向图：图中存在有方向边的图。边用表示由u到v的有向边，不等同于。 无向图：图中不存在有方向边的图。边用(u,v)表示由u到v的边，等

5、同于(v,u)。 度：与此点相连边的数量。 入度：终点为此点的边的数量。出度正相反。 子图：从原图中选出若干节点，其中两两点之间关系不变的图，叫做原图的子图。,洛谷网校冬令营 2018.2,Page 7,树的相关定义术语,树是由n (n =0)个结点组成的有限集合。0个节点的叫做空树，一般不研究。 结点的度（Degree）：结点的子树个数； 树的度：树的所有结点中最大的度数； 叶结点（Leaf）：度为0的结点； 父结点（Parent）：有子树的结点是其子树的根节点的父结点； 子结点/孩子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点； 兄弟结点（Sibling）：具有

6、同一个父结点的各结点彼此是兄弟结点；,洛谷网校冬令营 2018.2,Page 8,树的相关定义术语,路径和路径长度：从结点node1到nodek的路径为一个结点序列node1，node2，.，nodek。nodei是nodei+1的父结点。路径所包含边的个数为路径的长度； 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点； 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙； 结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1； 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度； 有序树

7、和无序树：若结点的子树有次序排列，且先后次序不能互换，这样的树称为有序树，反之为无序树。,洛谷网校冬令营 2018.2,Page 9,图论与oi,Noip2013 提高 货车运输 P1967 Noip2013 普及 车站分级 P1983 Noip2014 提高 联合权值 P1351 Noip2014 普及 寻找道路 P2296 Noip2015 提高 信息传递 P2661 Noip2015 提高 运输计划 P2680 Noip2016 提高 天天爱跑步 P1600 Noip2017 提高 逛公园 P3953 Noip2018 ？,洛谷网校冬令营 2018.2,Page 10,什么是图？,图由点

8、和边组成。根据边是否有方向，可分为有向图、无向图。树是特殊的无向图。 每条边可以有一个长度，当然也可以没有（默认为1）。 图论题面中顶点的个数通常用 n 表示，边的数量通常用 m 表示，数据范围一般不对n, m进行解释。 一般图论题n, m数量级为1e5（aeb为科学计数法，意思为a 10 。,有向图,无向图,洛谷网校冬令营 2018.2,Page 11,图的存储-邻接矩阵,我们选择用“邻接矩阵”表格的方式存储一个图。 存储规则：若a能到达b，则此表格第a行第b列的值就是a到b的距离（或1），无法访问为-1或正无穷。 特别的，自己到自己的距离为0。,有向图,无向图,洛谷网校冬令营 2018.2

9、,Page 12,图的存储-邻接矩阵,我们选择用“邻接矩阵”表格的方式存储一个图。 存储规则：若a能到达b，则此表格第a行第b列的值就是a到b的距离（或1），无法访问为-1或正无穷。 特别的，自己到自己的距离为0。,洛谷网校冬令营 2018.2,Page 13,图的存储-邻接表,邻接表（链式前向星）存储图比邻接矩阵更加高效。 邻接表由点表（由点构成的表）（上）和边表（由边构成的表）（下）组成。 Head数组存储的是以该点为起点（按照加入时间顺序）最后加入的一条边。 边表from数组实际操作没有用处，不过在查错环节 还是有用的。 Next数组是以该边起始点为起点的上一条边（按照 加入时间顺序）,

10、洛谷网校冬令营 2018.2,Page 14,树,什么是树啊？,洛谷网校冬令营 2018.2,Page 15,树,什么是树啊？ 树是一个特殊的图罢了，没啥了不起的。 特殊在这个n节点的图里，有n-1条连接图的边，把这些点连接起来。恰好这些点可以联通。 树的一些相关操作 树的重心和直径 倍增LCA（听说提高讲了那就算了） ,洛谷网校冬令营 2018.2,Page 16,树的存储方式,父亲节点表示法 儿子节点表示法 无向图表示 左儿子右兄弟 树转二叉树,1,2,1,6,8,7,3,4,5,2,3,6,4,5,7,8,洛谷网校冬令营 2018.2,Page 17,图的遍历,深度优先搜索 详见day5

11、搜索，此处不多讲述。 附深度优先搜索动画。,1,3,2,1,5,4,2,3,4,5,洛谷网校冬令营 2018.2,Page 18,图的遍历,广度优先搜索 详见day5搜索，此处不多讲述。 附广度优先搜索动画。,1,3,2,1,5,4,2,3,4,5,洛谷网校冬令营 2018.2,Page 19,BFS灌水法,usaco火情蔓延 一个R*C的方格图，时刻0时某些方格自燃，每秒钟向四个方向蔓延，问需要多少时间才使得整个方格图都在燃烧。 如图 由一个点向四周放射状发出，这就是bfs搜索的一种形式。详见day5 zcysky老师的搜索课。 提示，bfs在图论一般只适用于相邻两点之间距离为1的图。,洛谷

12、网校冬令营 2018.2,Page 20,图的最短路算法-Floyd,传递闭包 传递闭包和差分约束是一回事吗？ 当a能到达b，b能到达c，则a可以到达c。 当a到b的距离为dis1，b到c的距离为dis2，则至少存在路径使a到c的距离为dis1+dis2。,洛谷网校冬令营 2018.2,Page 21,图的最短路算法-Floyd,Floyd 算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或无向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。,洛谷网校冬令营 2018.2,Page 22,图的最短路算法-Floyd,初始化： 1. 不可以直接到达的d

13、is设为正无穷(oo)。 2. 自己到自己的距离为0。 3. 题目给定的边的disij直接赋值为该边长度。双向边需要disij和disji均赋值为边长。,洛谷网校冬令营 2018.2,Page 23,图的最短路算法-Floyd,Floyd算法使用的思想是： 枚举中转节点。 检查由S点经过此点到T点的路径是否比原先优。 更新由S点到T点的最短距离。,洛谷网校冬令营 2018.2,Page 24,图的最短路算法-Floyd,注：在oi中，由于正无穷在代码里难以表示，我们常将oo或inf定义为足够大的数字(0 x3f3f3f3f等)来表示正无穷。,5 K=1,5 K=1,2 K=1,7 K=1,14

14、 K=2,13 K=2,12 K=2,7 K=2,8 K=2,8 K=2,10 K=3,11 K=3,9 K=5,10 K=5,洛谷网校冬令营 2018.2,Page 25,图的最短路算法-Floyd,Q：为什么要先枚举K啊 A：这样便过早的把i到j的最短路径确定下来了，而当后面存在更短的路径时，已经不再会更新了。 假如我们求A到B的最短距离。 在内层枚举k：只有A-B唯一一条路线（因为咱们只能枚举一个中转点） 在外层枚举k：可以经过D求得A到C的距离，再经过C求得A到B的距离。,洛谷网校冬令营 2018.2,Page 26,图的最短路算法-Floyd,Q：怎么样输出最短路的方案啊？ A：我们

15、可以另开一个数组hisij，表示i到j点经过了hisij点。初始化时hisij=i即可。 维护：i到j的距离可以被更新时 hisij=k（枚举的中转节点）。 查询：递归查找：i到j其中一个中转节点是hisij，然后再找hisihisij和hishisijj直到这两个值为i或者j即可。,洛谷网校冬令营 2018.2,Page 27,图的最短路算法-Floyd,例题：香甜的黄油 P1828 题目简述：有n头牛住在p个牧场里，牧场两两之间有一定距离。现在FJ把所有奶牛集合在一个牧场里，请选择一个合适的牧场，使得所有奶牛迁移的总距离最小。输出最小值。 数据范围：n=500,p=800,牧场间道路条数m

16、=1450（无向图）,牧场间距离d=255。所有输入数据为正整数。,洛谷网校冬令营 2018.2,Page 28,图的最短路算法-Floyd,可以用Floyd没差。 统计一下每个牧场到底有多少奶牛，Floyd之后枚举每一个牧场作为最终牧场，计算迁移距离，最后取最小值即可。 复杂度Floyd p3 + 统计答案 p2 我洛谷AC不了，TLE70分，该怎么办啊？ 8003=5.12*108 5003=1.25*108 再过不了提交的时候开O2优化强行A掉吧，待会有好办法AC这道题。,洛谷网校冬令营 2018.2,Page 29,图的最短路算法-Floyd,例题：牛大赛 P2419 题目简述：给定n

17、头牛和m条胜负关系，求排名已定的牛的个数（和其他所有牛胜负关系已定）。 数据范围：n=100,m=4500。,洛谷网校冬令营 2018.2,Page 30,图的最短路算法-Floyd,Floyd 传递闭包。 胜利方向失败方连边，Floyd 改为tij|=tik 删去i, lca或j, lca上最大的一条边,洛谷网校冬令营 2018.2,Page 63,拿M元买啤酒，N元可以买一瓶，4个瓶盖换一瓶啤酒，2个空瓶换一瓶啤酒。可以向周围人无限制地借瓶盖和瓶子，但前提是必须归还同样的物品。比如借了一个瓶子，最后就要还一个瓶子，不能用两个瓶盖代替一个瓶子去还。你的目标是计算出最多能喝多少瓶酒。 N,M范围在int范围以内，保证M/N小于4e6。,休息题,洛谷网校冬令营