0x01 前置芝士🎂

0x02

Linux 文件？设备？

数学恶补
$\in $ 是属于，$G$ 是图，$V$ 是点，$E$ 是边

1. 基本概念

1.1 流网络，不考虑反向边

流网络 $G=(V,E)$ 是一个有向图，图中每一条边 $(u,v) \in E$ 有一个非负的容量值 $ c(u,v) \ge 0 $
且，若集合 $E$ 包含一条边 $(u,v)$ ，则不包含 $(v,u)$.

$(v,u) \in E \Rightarrow (u,v) \notin E$

1.2 可行流，不考虑反向边

1.2.1 两个条件：容量限制、流量守恒

1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量

1.2.3 最大流是指最大可行流

1.3 残留网络，考虑反向边，残留网络的可行流f’ + 原图的可行流f = 原题的另一个可行流

1.4 增广路径

1.5 割

1.5.1 割的定义

1.5.2 割的容量，不考虑反向边，“最小割”是指容量最小的割。

1.5.3 割的流量，考虑反向边，f(S, T) <= c(S, T)

1.5.4 对于任意可行流f，任意割[S, T]，|f| = f(S, T)

1.5.5 对于任意可行流f，任意割[S, T]，|f| <= c(S, T)

1.5.6 最大流最小割定理

1. 可行流f是最大流
2. 可行流f的残留网络中不存在增广路
3. 存在某个割(最小割)[S, T]，|f| = c(S, T)

1.6. 算法

1.6.1 EK O(nm^2)

1.6.2 Dinic O(n^2m)

1.7 应用

1.7.1 二分图

1. 二分图匹配
2. 二分图多重匹配

1.7.2 上下界网络流

1. 无源汇上下界可行流
2. 有源汇上下界最大流
3. 有源汇上下界最小流

1.7.3 多源汇最大流

1.排序模拟枚举

复杂度

• 一般（最坏）复杂度 ：记号为 O(……)
  均摊复杂度 $\qquad\quad\,$ ：记号为 Θ(……),但一般写成O(……)
• 约定
  1. 省略系数O(100n)=O(10n)=O($\frac{1}{2}$n)=O(n).
  2. log底数省略

递推，递归与分治

递推

1. 什么是递推

递推，就是从小的解开始，一步一步推到最优解的过程。

2. 如何递推

约定：本文的下标从1开始，代码尽量从1开始（我在努力习惯），一般使用$\LaTeX$美化

这一节主要介绍了一些基础的数据结构 （废话），前缀和，差分，二分查找，离散化，ST表，线段树等。

来给大家一一介绍一下

课件：

Link To Problem

可怜的小狗🐕

强联通

1. 对于一些存在依赖关系的模型，若其建图是一个DAG，则可以直接通过拓扑排序解决，但若其中有环则需要特殊处理