进阶课的笔记，y总讲的很好！大约记了一下方便复习
试听课 本节内容

流网络 $G=(V,E)$

• 有向图
• 两个特殊点，源点和汇点
• 边的属性为容量，表示最大能够通过的水量(或其他限制条件)
• 源点：有很多流量流出
• 汇点：聚集流量
• 先不考虑反向边(假定不存在反向边)
• 如果有反向边，通过加点变成没有反向边的图
• 如果某条边不存在，流量为$0$

可行流 $f$

要满足的条件：
- 容量限制 $0<=f(u,v)<=c(u,v)$
- 流量守恒：除源点和汇点外，其余点的流量流出流入都相同，不存储流量

暂时不考虑反向边
- $|f|$表示可行流的流量值，定义为从源点流出的流量或汇点流入的流量
- $|f|=\sum_{(s,v)\epsilon E}f(s,v)-\sum_{(v,s)\epsilon E}f(v,s)$

最大流

• 流量最大的可行流

残留网络 $G_f$

• 是针对流网络的某一条可行流来说的
• 可行流不同，残留网络不同
• 残留网络点击包含原网络所有点，边包括原网络所有边和所有反向边
• 每条边的容量如何定义呢；
• $c1(u,v)=c(u,v)-f(u,v),(u,v) \epsilon E$ 表示还有多少流量可以用，流量减去容量
• $c1(u,v)=f(v,u),(v,u)\epsilon E$ 反向边表示可以退回去多少流量
• 设残留网络的可行流为$f1$，则$f1+f$也是原网络$G$的另外一个可行流
• $|f+f1|=|f|+|f1|$
• 流量相加指的是每条边对应相加：残留网络和原网络边的方向相同，累加；相反，相当于退回的流量，减去；
• 如何证明是可行流呢？从容量限制和流量守恒来看；

增广路径

• 残留网络里，沿着流量$>=0$的边能够走到终点，这样的路径为增广路径
• 无环
• 性质：对于当前的可行流来说，残留网络里无增广路径，则该可行流为最大流

割

• 定义：将点集分为不重不漏的两部分$S,T$，使得源点和汇点分别属于不同的部分
• 割的容量：所有从$S->T$的边的容量之和，即$c(S,T)=\sum_{u\epsilon S}\sum_{v \epsilon T}c(u,v)$。有向！
• 容量不考虑反向边
• 最小割指的是最小割的容量
• 割的流量:$f(S,T)=\sum_{u\epsilon S}\sum_{v \epsilon T}f(u,v)-\sum_{u\epsilon T}\sum_{v \epsilon S}f(u,v)$；$S->T$的流量减去$T->S$的流量
• 流量考虑反向边
• $f(S,T)<=c(S,T)$，割的流量小于等于割的容量

对于任何可行流$f$,任何割$[S,T],|f|=f(S,T)$。可行流的流量等于割的流量。
一些性质：
- $f(X,Y)=\sum_{u\epsilon X}\sum_{v \epsilon Y}f(u,v)-\sum_{u\epsilon Y}\sum_{v \epsilon X}f(u,v)$
- $f(X,Y)=-f(Y,X)$ 相当于符合取反
- $f(X,X)=0$ 前后会抵消
- $f(Z,X\&Y)=f(Z,X)+f(Z,Y)$ $X,Y$无交集，可以分别算

证明：
设$S\cup T=V,S\cap T=\phi$
则$f(S,V)=f(S,S\cup T)=f(S,S)+f(S,T)$
$f(S,S)=0$
所以$f(S,T)=f(S,V)=f(s,V)+f(S1,V)$,其中$s$表示源点，$S1=S-s1$
$f(s1,V)=\sum_{u\epsilon S1}(\sum_{v\epsilon V}{f(u,v)}-\sum_{v\epsilon V}{f(v,u)})$
因为$s1$的点不包括源点，所以点流量守恒，$f(s1,V)=0$
$f(s,V)=|f|=f(S,T)$

对于任何可行流$f$,任何割$[S,T],|f|<=c(S,T)$
# 最大流最小割定理
知道其中一个可以推出另外两个：
1. 可行流$f$最大流
2. 可行流的残留网络$G_f$里不存在增广路
3. 存在某个割$(S,T)，|f|=c(S,T)$；可行流流量等于割的容量

证明：

$1->2$：

如果$G_f$中存在增广路，
说明存在一个$f1$也是可行流，
最大流应该是$f1+f,|f1+f|=|f|+|f1|>|f|$
与$1$矛盾

$3->1$：

对于任何可行流$f$,任何割$[S,T],|f|<=c(S,T)$；
也就是说最大流也小于等于$c(S,T)$；
最大流$>=|f|$；
$f=c(S,T)>=$最大流,
所以$f$是最大流。
- 最大流$<=$最小割，最小割$<=c(S,T)=|f|<=$最大流。最大流等于最小割

$2->3$

• $S$集合：在残留网络里，从$s$出发沿着容量$>0$的边能够遍历到的所有点
• $T=V-S$
• 这样就是一个合法的割
• 对于$x\epsilon S,y\epsilon T,f(x,y)=c(x,y)$
• 对于$y\epsilon S,x\epsilon T,f(x,y)=0$
• $|f|=f(S,T)=\sum_{u\epsilon S}\sum_{v \epsilon T}f(u,v)-\sum_{u\epsilon T}\sum_{v \epsilon S}f(u,v)=\sum_{u\epsilon S}\sum_{v \epsilon T}c(u,v)=c(S,T)$

EK算法 $O(nm^2)$

• 找增广路
• 更新残留网络
  技巧：
• 正向边和反向边成对加，方便快速找反向边

const int maxn = 2e5 + 7;
struct node{
        int e,ne,w;
};
struct EK{
    int h[maxn],n,m,idx;
    node edge[maxn];
    int S,T,maxflow=0;
    int vis[maxn],incf[maxn],pre[maxn];
    void init(){
        memset(h,-1,sizeof h);
        idx=0;
    }
    void add(int u,int v,int w){
        edge[idx]={v,h[u],w};h[u]=idx++;
    }
    int bfs(){///找到增广路
        memset(vis,0,sizeof vis);
        queue<int>q;
        q.push(S);vis[S]=1;
        incf[S]=inf;///源点的流量是无限的
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=h[u];~i;i=edge[i].ne){
                int j=edge[i].e;
                if(edge[i].w){///当前边容量大于0
                    if(vis[j]) continue;///被访问过
                    incf[j]=min(incf[u],edge[i].w);///最大可行流为最小值
                    pre[j]=i;///记录前驱结点
                    q.push(j);vis[j]=1;
                    if(j==T) return 1;
                }
            }
        }
        return 0;
    }
    void update(){
        int x=T;
        while(x!=S){
            int y=pre[x];
            edge[y].w-=incf[T];///减去增广路的最小流量
            edge[y^1].w+=incf[T];///反向边
            x=edge[y^1].e;
        }
        maxflow+=incf[T];
    }
};

int main()
{
    EK ek;
    ek.n=read;ek.m=read;ek.S=read;ek.T=read;
    ek.init();//初始化
    for(int i=1;i<=ek.m;i++){
        int u=read,v=read,w=read;
        ek.add(u,v,w);ek.add(v,u,0);//连续存图
    }
    while(ek.bfs()) ek.update();//不断找增广路更新残留网络
    printf("%d\n",ek.maxflow);//求最大流
    return 0;
}