超级源汇
最常用的手段，建立超级（虚拟）源汇点，向图中点连边。
大部分的题目基本都要建立超级源汇点。
超级源汇的实际意义是限制数量。
拆点
顾名思义，就是将原图中的一个点拆成两个或以上的点，在最小割中十分常见。
- 入点和出点
经常有这一类问题，一个图给出了点权而不是边权，我们在连接边的时候就显得十分不好操作，这个时候我们往往就会有这样一种操作，把每个点拆成入点和出点，题目给出的连边均由每个点的出点连向入点，然后每个点的入点和出点之间连一条流量为点权的边，就可以满足点权的限制了。
- 根据时间拆点
有一部分题目是这样的，我们给出的图的同时也给出了一个天数或者时间的限制，然后对每一天做出询问，最后求总和，很明显的一点是，要把每一天都连向汇点然后求出总和。
这个时候我们发现，如果其他的点仅仅只是一个点的话，无法满足求出每一天这个要求，因为会互相影响，这个时候我们就相应的把这些点拆成天数这么多个点，然后分别向向对应的天数连边。
- 根据时间段拆点
这种拆点方式主要是在费用流里出现，因为有很多这种题目，就是一个人在不同的流量是费用是不一样的，所以为了满足这个要求，就把这个人拆成一共有多少不同费用的点。
举个例子：你们数学老师今天布置作业越多，你的不满值越大，如果是5张以下，一张卷子增加1点不满值，如果10张以下，一张卷子增加两点，如果10张以上，那么一张卷子增加\(+\infty\)点不满值。那么我们就把你拆成三个点，分别对应三种不满值。
枚举和二分
- 枚举和二分流量
有这样一部分题目，它给你的图不一定是完整的，往往需要你确定一个值来确定是否能够跑出期望的最大流。
就比如说去计算一个最少的时间或者花费时，我们并没有一个具体的数值，这个时候我们往往预先通过连接$+\infty $先跑一遍最大流，之后二分时每次重构图，再次跑最大流，并且通过此时的流量是否和刚才相等来调整二分的上下界。抑或跟人数有关的题目，我们二分的时候判断最大流是否等于当前人数。
然后枚举的建图方法就更是简单，每次枚举时重构图，然后一直跑到不能再跑了为止。
- 枚举和二分费用
费用流的题目中，有些题目会给你费用的限制，或者说是间接的控制了你的流量，比如说他要一个满足条件时可能的最小费用，你仍然可以像刚才二分流量时那么跑。但是它也有可能要一个不超过一个费用时能满足的最大条件，这个时候去二分那个条件，然后控制费用。
- 枚举和二分边和点
有的题目里，各个点的添加是有顺序的，每个点的边的添加也可能是有顺序的，这个时候就有一类问题会让你确定一个值，要这个值之前的所有点可以满足最大流量，这个时候我们就要二分加入图中的点了，边也是同理。不过总的来说，二分的方法万变不离其宗，总是要通过流量或者费用调整二分上下界。
点的构造
大部分题目是有迹可循的，因为他们至少有点或者有明显能够当做点的状态。或者题目给出的点就真的能够当成点使用。但是也有的题目，并没有明显的点的提示，或者给出的你明显的点完全不能够当成网络流里的点使用。对于这种题目，我们就要自己构造出来一些新的点来进行网络流。
这类问题比较灵活，比如在网格图中，可以将行和列建成点；在与时间有关的题目中，可以将时间建成点；还可以把一堆点当作一个点等等。
动态建图
有一些题目是这个样子的，他们往往有着较其他网络流题目更大的数据，并且他们也有一个特点，就是在一部分边连好之后，之后是先建建图或者是跑一个点再加一个点这么建图对最终结果并没有影响。这样一来我们就可以通过动态加点或者边的方式使其满足题目要求的复杂度。
当然，动态建图也是有要求的：
- 数据范围不能过大
虽说是减小了时间复杂度，但是也只是减少了部分，很多情况下复杂度的等级并没有变化，只是因为在大部分操作里减少了一些不必要的操作使速度加快。
- 主要应用于费用流
大多时候动态加点的题目都是费用流题目，原因就是最短路一次基本上也就只能增广出来一条增广路，如果是网络流的话，dinic的当前弧优化往往能够取到更好的效果。费用流由于大部分人都会使用EK的朴素算法，所以动态加点可以是速度提高好几个档次。
- 当前最优原则
即前面点的选择不会影响后面的选择。这是因为在跑网络流的时候，不可避免的后面跑的点回合前面跑的点有冲突，这个时候我们可以通过反边来使冲突化解。那么如果我们一个一个的加点，很明显就没办法满足这个条件。但是如果我们可以确定当前这个点跑了这个流，后面的点跑这个流的一定不如这个点优，那么我们就可以无视那个冲突了。
二分图
- 定义
二分图又称作二部图，是图论中的一种特殊模型。 设\(G=(V,E)\)是一个无向图，如果顶点\(V\)可分割为两个互不相交的子集\((A,B)\)，并且图中的每条边\((i,j)\)所关联的两个顶点\(i\)和\(j\)分别属于这两个不同的顶点集\((i \in A,j\in B)\)，则称图\(G\)为一个二分图。
最小点覆盖：即在所有顶点中选择最少的顶点来覆盖所有的边。
最大匹配：二分图左右两个点集中，选择有边相连的两个匹配成一对（每个点只能匹配一次），所能达到的最大匹配数。
独立集：集合中的任何两个点都不直接相连。
最大权匹配：指二分图中边权和最大的匹配。
- 二分图最大匹配
将源点连上左边所有点，右边所有点连上汇点，容量皆为 \(1\)，原来的每条边从左往右连边，容量也皆为\(1\)，最大流即最大匹配。
二分图中，最小点覆盖\(=\)最大匹配。
二分图中，最大独立集\(=\)原图总点数\(-\)最大匹配。
- 二分图最大权匹配
可以转化为费用流。
首先在图中新增一个源点和一个汇点。
从源点向二分图的每个左部点连一条流量为\(1\)，费用为\(0\)的边，从二分图的每个右部点向汇点连一条流量为\(1\)，费用为\(0\)的边。
接下来对于二分图中每一条连接左部点\(u\)和右部点\(v\)，边权为\(w\)的边，则连一条从\(u\)到\(v\)，流量为\(1\)，费用为\(w\)的边。
求这个网络的最大费用最大流即可得到答案。
- 删边
在一个二分图中，如果删去一条边能够使这个图的最大匹配减小\(1\)的话，那么这条边一定在残量网络中满流，并且它所连接的两个点一定不在同一个强连通分量当中。
首先满流的条件一定要有，不满流那这条边就不在最大匹配里了。然后就是不在同一个强连通分量里这个条件，我们可以发现，在同一个强连通分量里的话，那他们就可以自己在这个强连通分量的内部进行增广，也就是说我们可以通过操作从而找到另一组最大匹配并且不需要使用当前这条边，所以这条边删掉也就无可厚非了。
- 最小路径覆盖
就是现在有一个有向无环图\(G\)，要求用尽量少的不相交的简单路径覆盖所有的节点 。
结论：最小路径覆盖\(=\)原图总点数\(-\)最大匹配。
最大匹配：
我们对当前的图拆点，把每个节点都拆成\(x,y\)两个节点。如果\(x_1\)有一条指向\(x_2\)的边，那么就把\(x_1\)和\(y_2\)之间连一条边，这样我们就能得到一个二分图了，那么为什么这么做可行呢？
这是因为一开始每个点都是独立的为一条路径，总共有\(n\)条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了\(1\)。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖\(=\)原图总点数\(-\)新图的最大匹配数。
黑白染色
- 适用性
黑白染色一定是在棋盘图上。把棋盘的格子当做点，并且经过了染色之后，黑点只会限制白点，不会限制黑点，白点也只会限制黑点。也就是说同色的点之间并没有直接关系。
- 作用
黑白染色，一共只有两种颜色，所以这样建图之后一般都会和二分图非常像，然后就是随便匹配的事了。另一种情况是你把这题转化成了一个最小割的模型，发现题目中删去某个点或者添加某个点的操作就是在删边。从而随便网络流跑出来这个题。
- 难点
有的时候发现黑白染色并不能完全解决问题，或者说这个题并不能符合黑白染色的定义。那么我们就红黄蓝染色，再不行就红黄绿蓝染色。然后重新构造模型。不得不说，这东西有的时候还是能派上大用的。
- 时间复杂度
因为建出来的图近似于稀疏的二分图，所以时间复杂度往往近似于\(O(n\sqrt n)\)。
其他
- 最大权闭合子图
- 最长反链和最小链覆盖
- 优化建图
- 最大密度子图
- 欧拉图与欧拉回路