一、分层图分层图只是建图时有区别，但跑最短路板子都是一样的，正所谓图论最难的就是建图，只要有合适的建图方法，那么问题就很简单了。分层图是指有很多个平行的图，各个平行的图之间有特殊的连接边。用分层图的几种情况：1、有k个不同集合的边，将每个集合内的边建成一张图，再建立第k+1个图，是一个虚层，用这个虚层将这k张图连接起来。每次可以通过虚层转移到另一个集合的图中。如例1.小雨坐地铁。2、有k个机会使得

一、网络流与最大流网络流（network-flows）是一种类比水流的解决问题方法，与线性规划密切相关。在一个有向图中，一个源点S到一个汇点T之间有连边，边的权值是该边的最大容量，网络流就是从S点到T点的一个可行流。网络流最初的问题就是研究最大流，就是指所有可行流里面最大的流。举个简单的例子，如下图：若v1到v6六个点表示的是六个城市，每条边的权值表示的是城市之间路的长度，选择要运送一批物资从v1