最大流定义见网络流基本概念

$$\huge最大流$$

$EK算法$

$由于最大流中一定没有增广路$

$可以不断从源点出发寻找增广路$

$并在残余网络上修改$

$直到不存在增广路为止$

$时间复杂度 O(nm^2)$

$EK模版$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 20010, inf = 0x3f3f3f3f;

int n, m, s, t;
int h[N], e[M], c[M], ne[M], idx;
int q[N], d[N], pre[M];
bool st[N];

void add(int u, int v, int w)//在残余网络上建边
{
    e[idx] = v, c[idx] = w, ne[idx] = h[u], h[u] = idx ++ ;
    e[idx] = u, c[idx] = 0, ne[idx] = h[v], h[v] = idx ++ ;
}

bool bfs()//寻找增广路
{
    memset(st, 0, sizeof st);

    int hh = 0, tt = 0;
    q[0] = s, st[s] = true, d[s] = inf;

    while (hh <= tt)
    {
        int u = q[hh ++ ];
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j] && c[i])
            {
                st[j] = true;
                pre[j] = i;
                d[j] = min(d[u], c[i]);
                if (j == t)return true;
                q[++tt] = j;
            }
        }
    }
    return false;
}

int EK()
{
    int res = 0;
    while (bfs())
    {
        res += d[t];
        for (int i = t; i != s; i = e[pre[i] ^ 1])
            c[pre[i]] -= d[t], c[pre[i] ^ 1] += d[t];//在残余网络上修改
    }
    return res;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }

    printf("%d\n", EK());

    return 0;
}

$Dinic算法$

由于EK每次只能搜索1条增广路

在EK算法的基础上,建立分层图,并搜索多条增广路

$Dinic模版$

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = 200010, inf = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], c[M], ne[M], idx;
int q[N], dep[N], cur[N];

void add(int u, int v, int w)
{
    e[idx] = v, c[idx] = w, ne[idx] = h[u], h[u] = idx ++ ;
    e[idx] = u, c[idx] = 0, ne[idx] = h[v], h[v] = idx ++ ;
}

bool bfs()
{
    memset(dep, -1, sizeof dep);
    int hh = 0, tt = 0;
    q[0] = S, dep[S] = 0;
    cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dep[j] == -1 && c[i] > 0)
            {
                dep[j] = dep[t] + 1;//建立分层图
                cur[j] = h[j];
                if (j == T)return true;
                q[++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)//寻找增广路
{
    if (u == T)return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;//当前弧优化
        int j = e[i];
        if (dep[j] == dep[u] + 1 && c[i] > 0)
        {
            int t = find(j, min(c[i], limit - flow));
            if (!t) dep[j] = -1; //废点优化
            c[i] -= t, c[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

void dinic()
{
    int res = 0, flow;
    while (bfs()) while (flow = find(S, inf))res += flow;
    printf("%d\n", res);
}

void build()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    //TODO:建边
}

int main()
{
    build();
    dinic();
    return 0;
}