Dinic 算法

算法描述：

对于 $n$ 个节点，$m$ 条边的流网络，可以在 $O(n^2m)$ 的时间复杂度内求出该流网络的 最小割。

Dinic 算法其实是求最大流的重要算法，这里同样能用来求最小割，原因是我们已经证明出了任何一个流网络中 最大流 $=$ 最小割，详细参考 网络流的基本概念

算法步骤：

Dinic 算法其实是 EK 算法的一个暴力的优化，EK 算法每次只能搜索一条增广路径，Dinic 算法每次都用爆搜的形式尽可能多的搜索增广路径。

而图中可能存在环，为了保证爆搜的过程中不会造成死循环，这里可以使用分层图，这样每次都是一层一层往下搜索，就不会出现死循环。

1. bfs 建立分层图
2. dfs 找出所有能增广的路径
3. 累加最大流量

注意： Dinic 算法对于优化非常敏感，如果优化的不好就可能直接 TLE

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

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

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表维护残量网络
int q[N]; //队列
int d[N]; //记录每个节点到起点的距离，分层图
int cur[N]; //当前弧：cur[i] 记录 h[i] 指向的链表中指针的位置，即节点i当前枚举到的边

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(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S]; //每个节点最开始的当前弧就是枚举的第一条边，即所指向链表的表头

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

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1; //建立分层图
                cur[j] = h[j]; //初始化当前弧

                if(j == T) return true; //找到终点说明存在增广路径

                q[++tt] = j; //没找到就继续扩展
            }
        }
    }
    return false; //到这说明走不到终点，不存在增广路径
}

int find(int u, int flow) //搜索从 u 节点往终点传输的最大流量，flow 表示当前传输到 u 节点的流量
{
    if(u == T) return flow; //如果传输到了终点，那么 flow 就是当前分支能传输的最大流量

    int rest = flow; //记录当前剩余的没有往下传输的流量，最开始是所有传输到 u 的流量
    for(int i = cur[u]; i != -1 && rest; i = ne[i]) //枚举下一层中的边，直到没有剩余流量或遍历所有边
    {
        //当前弧优化：枚举到第i条边，说明 h[u] 中在第i条边前面的边都已经传输完流量，不需要再枚举
        cur[u] = i;

        int j  = e[i];
        if(w[i] && d[j] == d[u] + 1) //如果当前边能传输流量，且对应下一层
        {
            int k = find(j, min(rest, w[i])); //搜索当前分支能往终点传输的最大流量
            if(!k) d[j] = 0; //如果当前分支无法往终点传输流量，说明当前分支不需要再枚举，移出分层图

            w[i] -= k; //当前边减去往下传输的流量
            w[i ^ 1] += k; //反向边加上往下传输的流量
            rest -= k; //剩余能传输的流量减去往下传输的流量
        }
    }
    return flow - rest; //从 u 节点能往终点传输的流量 = 传输到 u 节点的流量 - 剩余没有往下传输的流量
}

int dinic() //dinic算法求最小割
{
    int maxf = 0, flow; //maxf 记录最小割容量
    while(bfs()) //只要存在增广路径
        while(flow = find(S, INF)) maxf += flow; //尽可能多的用增广路径更新
    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", dinic());

    return 0;
}