1. 网络
    (1)流网络G（不考虑反向边）

    (2)残留网络Gf（考虑反向边，正向边的值=原网络容量值-流量值，反向边的值=原网络中的流量值）


可行流满足两个条件：1.流量值不超过容量值  2.对于出了源点和汇点以外的点，其流入=流出
其流量值 指 从源点流出的流量 - 从源点流入的流量


2. 可行流 和 最大流
    (1)流网络的可行流：f

    (2)残留网络的可行流：f'

    (3)最大流：原网络中最大可行流

    (4)可行流流量：|f|


3. 增广路径：在残留网络中，沿着容量大于0的遍走，能从源点走到汇点，则该条路径叫增广路径


4.割
    (1)割：把原网络中的点集V分为两部分S和T（满足 S并T=V  S交T=空集），使得源点s属于S，汇点t属于T

    (2)割的容量：(不考虑反向边)所有从点集S指向点集T的边，记为 c(S,T)

    (3)割的流量：(考虑反向边)所有从S到T的可行流 - 所有从T到S的可行流，记为 f(S,T)

    (4)最小割：最小割的容量（因为分割的方式有很多种）


性质：
1. f + f'仍是原来流网络的可行流(|f + f'| = |f| + |f'|)

2. 如果存在增广路径(存在f'(不等于0))，则说明f一定不是最大流; 反之易推是最大流！

3. 对于任意一个割，其 割的流量 一定<= 割的容量，即f(S,T) <= c(S,T)

4. 对于任意割[S,T]，任意可行流f：割的流量 = 可行流流量，即 f(S,T) = |f|

5. 由3 4可得，对于任意割[S,T]，任意可行流f：|f| <= c(S,T)

6. 由5可得，最大流 <= 最小割，即 最大可行流量 <= 最小割容量

7. 最大流最小割定理：（对于一个流网络G=(V,E)）
    (1)可行流f是最大流
    (2)残留网络Gf中不存在增广路径
    (3)存在一个割[S,T]，使得 |f| = c(S,T)（即可行流流量 = 割的容量）（其中隐含了 最大流 = 最小割）
   这3个东西相互等价！！！(1) <=> (2) <=> (3)


问：建完图后如何证明是正确的？
答：定义两个集合，一个表示问题P，一个表示建的图G，P集合中的可行解 是否<=> G集合中的可行流；
    如果等价，则原问题中的最大值，就是G中的最大流。
最小割的题也是如此！


问：如何输出最大流的路径？
答：最后跑完图，最大流表示该最大流中的正向边的容量为0（被榨干了）
    for(int i=0; i<idx ;i+=2)   //枚举所有的正向边（基于我们的建图方式）
        if(!f[i])               //是最大流的边（该边的容量是0）
            cout<<e[i ^ 1]<<' '<<e[i]<<endl;    //e[i]是右边的点，e[i ^ 1]是左边的点


--------------------------分界线（上面是概念，下面是算法）---------------------------------



算法1：（EK算法 找最大流）(时间复杂度虚高O(n*m^2)，处理n+m处于1000 ~ 10000之间)
维护残留网络，一直迭代，每次在残留网络找增广路径，然后更新残留网络，直到找不到为止，此时的路径就是最大流。

(1) 如何找增广路径？     bfs就行
(2) 如何更新残留网络？   
    当前我们找到了一条增广路径，然后要把这条增广路径更新掉，即该增广路径上的边都减去该增广路径上的最小值；
    设当前增广路径上边的最小值为k，对于残留网络的每条边，正向边c1，反向边c2；则c1变成c1-k，c2变成c2+k
(3) 如何建残留网络？     每条边还要存一下容量，然后正向反向成对建，这样^1就成对变换

--------------------------------------------------------------------------------------------

算法2：（dinic算法 找最大流）(时间复杂度虚高O(n^2*m)，处理n+m处于10000 ~ 100000之间)
思想和EK算法一样，只是我们找增广路径的时候同时找多条，然后同时更新。
为了避免环，我们引入分层图：a -> b，如果a是第i层，则b是第i+1层，而且只有当前点的层数没有被更新过，才会赋予层数。

(1) 建图什么的跟EK算法一样
(2) 先bfs 判断是否有增广路径，同时建出分层图
(3) 然后对于残留网络的分层图，我们dfs找出所有能增广的路径，然后把能加的流量加上去
(4) 然后继续迭代，看一下下一次残留网络中是否有增广路径

关于优化：
(1) 当前弧优化：cur[i] = j 表示点i从j开始枚举，这样我们每次枚举时就不用从头枚举边了
(2) 对于find()=0，则表示从当前点 到 T没有增广路径了，则该点其实可以删掉（d[] = -1）
注意：dfs就是相当于，假设u向后有很多条增广路径，然后我们同时找，然后回溯时同时累加然后同时更新。