EK求最大流

算法步骤：

用 while 循环不断判断残量网络中是否存在增广路径。

对于循环中：

1. 找到增广路径
2. 更新残量网络
3. 累加最大流量

循环结束，得出最大流。

lyd写法

/*
本题就是一个Edmonds-Karp算法求最大流的模板题，直接套模板即可。
*/

#include <iostream>
#include <cstring>

using namespace std;

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

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表，e[i] 表示第i条边上的剩余容量
int incf[N]; //incf[i] 表示从S到i的增广路上所有边的最小剩余容量
int q[N]; //队列
int pre[N]; //pre[i] 表示当前增广路中节点i的前驱边
bool st[N]; //标记数组
int maxf; //记录最大流量

void add(int a, int b, int c) //在a到b之间添加一条流量容量为c的边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; //正向剩余流量容量为c的边
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++; //反向剩余流量容量为0的边
}

bool bfs() //判断是否还存在增广路，即从S到T且不经过流量容量为0的边的路径
{

    int hh = 0, tt = 0;
    q[0] = S; //从起点开始

    memset(st, 0, sizeof st);
    st[S] = true;

    incf[S] = INF; //最开始没有经过任何边，最小剩余容量设置为正无穷

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
            if(w[i]) //只有当前边还有剩余流量才能走
            {
                int j = e[i];
                if(st[j]) continue; //已经搜索过的点跳过

                incf[j] = min(incf[t], w[i]); //更新经过的最小剩余容量
                pre[j] = i; //记录前驱边
                q[++tt] = j; //扩展
                st[j] = true; //标记

                if(j == T) return true; //如果能走到终点，说明存在增广路径
            }
    }
    return false; //到这说明不存在增广路径
}

void update() //更新网络中的剩余流量情况
{
    int u = T; //倒推增广路径
    while(u != S)
    {
        int i = pre[u];
        w[i] -= incf[T]; //正向边减去能减去的最大流量
        w[i ^ 1] += incf[T]; //反向边加上对应的流量
        u = e[i ^ 1]; //回推
    }
    maxf += incf[T]; //将当前流量累加到结果中
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);

    memset(h, -1, sizeof h); //初始化邻接表

    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); //添加边
    }

    while(bfs()) update(); //只要存在增广路径就更新网络
    printf("%d\n", maxf);

    return 0;
}

y总写法

#include <iostream>
#include <cstring>

using namespace std;

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

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
//q[] 表示队列
//d[i] 表示从 S 能传输到 i 的最大流量
//pre[i] 表示 i 的前驱边
//st[i] 表示 i 是否被遍历过
int q[N], d[N], pre[N];
bool st[N];

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; //正向边
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++; //反向边
}

bool bfs() //判断是否存在增广路径
{
    //初始化队列
    int hh = 0, tt = 0;
    q[0] = S;

    //初始化标记
    memset(st, 0, sizeof st);
    st[S] = true;

    //源点能传输无穷无尽的流量
    d[S] = INF;

    while(hh <= tt) //bfs
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            //如果当前点还没被搜索过，且这条边流量 > 0，说明可以从这条边往下传输流量
            if(!st[j] && w[i])
            {
                d[j] = min(d[t], w[i]); //更新能传输的最大流量
                st[j] = true; //记录被搜索过
                pre[j] = i; //记录前驱边

                if(j == T) return true; //走到汇点说明找到一条增广路径
                q[++tt] = j;
            }
        }
    }
    return false; //到这说明不存在增广路径
}

int EK() //求最大流
{
    int maxf = 0; //记录最大流量
    while(bfs()) //如果存在增广路径
    {
        maxf += d[T]; //累加当前增广路径能传输到汇点的流量
        for(int i = T; i != S; i = e[pre[i] ^ 1]) //回推整条增广路径，并更新路径上所有边的容量
            w[pre[i]] -= d[T], w[pre[i] ^ 1] += d[T]; //正向边减去输送过去的流量，反向边加上能往回输送的流量
    }
    return maxf; //返回最大流量
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);

    memset(h, -1, sizeof h); //初始化邻接表

    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); //添加边
    }

    printf("%d\n", EK()); //Edmonds-Karp算法

    return 0;
}