最大流EK算法

容量网络

设G(V,E),是一个有向网络;

在V中指定了一个顶点,称为源点(记为Vs),以及另一个顶点,称为汇点(记为Vt);

对于每一条弧属于E,对应有一个权值c(u,v)>0,称为弧的容量.

通常把这样的有向网络G称为容量网络.

弧的流量

通过容量网络G中每条弧,上的实际流量(简称流量),记为f(u,v);

网络流

所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流

可行流(与流网络性质)

在容量网络G中满足以下条件(1、3)的网络流f,称为可行流 (123为流网络性质)

容量限制：对任意u,v∈V，f(u,v)≤c(u,v)。

反对称性：对任意u,v∈V，f(u,v) = -f(v,u)。从u到v的流量一定是从v到u的流量的相反值。

流守恒性：对任意u，若u不为S或T，一定有∑f(u,v)=0，(u,v)∈E。即u到相邻节点的流量之和为0，因为流入u的流量和u点流出的流量相等，u点本身不会”制造”和”消耗”流量

最大流

在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.

如何求最大流？(何为增广路)

假如所有边上的流量都没有超过容量（水管），那么就把这个流，称为一个可行流。

易见，任一网络中都有一个零流，即每弧a上f(a)=0的流f.

我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点(这条路叫做可行路径)，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta，一定可以保证这个流依然是可行流，这是显然的。

这样我们就得到了一个更大的流，他的流量是之前的流量+delta，而这条路就叫做增广路

基本思想

每次寻找增广路(就是源点到汇点的一条可行路)然后ans+=增广路能流过的流量，更新剩余网络，然后再做增广路，直到做不出增广路。

反向边

加条反相边那就是给程序一个反悔的机会

现实中，反相边是不存在的，只是在程序中出现

残余（残量）网络

在一个网络流图上，找到一条源到汇的路径（即找到了一个流量）后，对路径上所有的边，其容量都减去此次找到的量，对路径上所有的边，都添加一条反向边，其容量也等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”

为什么要加反向边？

在做增广路时可能会阻塞后面的增广路…或者说做增广路本来是有个顺序才能找完最大流的…..但我们是任意找的…为了修正…就每次将流量加在了反向弧上…让后面的流能够进行自我调整…剩余网络的更新(就在原图上更新就可以了)

据说是Ford-Fulkerson算法的改进，EK = SAP(Shortest Augmenting Path 最短增广路)

Code(模板)易MLE、TLE O(n m m)

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 205;
const int INF = 0x3f3f3f3f;

///点、路、源点、汇点
int n, m, s, t;
int pre[N];
int r[N][N];    ///残余网络
bool vis[N];

///寻找一条从s到t的增广路，若找到返回true
bool bfs(int s, int t)
{
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    vis[s] = 1;
    q.push(s);
    while(q.size())
    {
        int first = q.front();
        q.pop();
        for(int i = 1; i <= n; ++i)
            if(!vis[i] && r[first][i] > 0)
            {
                pre[i] = first;
                vis[i] = 1;
                if(i == t)
                    return 1;
                q.push(i);
            }
    }
    return 0;
}

int EK(int s, int t)
{
    int flow = 0, d, i;
    while(bfs(s, t))
    {
        d = INF;
        for(i = t; i != s; i = pre[i])///i != s
            d = min(d, r[ pre[i] ][i]);
        for(i = t; i != s; i = pre[i])
        {
            r[ pre[i] ][i] -= d;
            r[i][ pre[i] ] += d;
        }
        flow += d;
    }
    return flow;
}

int main()
{
    while(~scanf("%d%d%d%d", &n, &m, &s, &t))
    {
        int u, v, w;
        memset(r, 0, sizeof(r));
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            r[u][v] += w;       /// = will WA
        }
        cout << EK(s, t) << '\n';;
    }
    return 0;
}

参考博客：

思想 https://www.cnblogs.com/pk28/p/8039645.html

定义 https://blog.csdn.net/x_y_q_/article/details/51999466

概念 https://blog.csdn.net/A_Comme_Amour/article/details/79356220

过程 https://blog.csdn.net/wzw1376124061/article/details/55001639