最大流

网络流中最常见的问题就是网络最大流。假定从源点流出的流量足够多，求能够流入汇点的最大流量。解决这个问题最常用的是Ford-Fulkerson算法及其优化。

洛谷模板：https://www.luogu.com.cn/problem/P3376

DFS

用dfs实现的FF算法时间复杂度上界是 $O(ef)$ ，其中 e 为边数，f为最大流。

int n, m, s, t; // s是源点，t是汇点
bool vis[MAXN];
int dfs(int p = s, int flow = INF)
{
    if (p == t)
        return flow; // 到达终点，返回这条增广路的流量
    vis[p] = true;
    for (int eg = head[p]; eg; eg = edges[eg].next)
    {
        int to = edges[eg].to, vol = edges[eg].w, c;
        // 返回的条件是残余容量大于0、未访问过该点且接下来可以达到终点（递归地实现）
        // 传递下去的流量是边的容量与当前流量中的较小值
        if (vol > 0 && !vis[to] && (c = dfs(to, min(vol, flow))) != -1)
        {
            edges[eg].w -= c;
            edges[eg ^ 1].w += c;
            // 这是链式前向星取反向边的一种简易的方法
            // 建图时要把cnt置为1，且要保证反向边紧接着正向边建立
            return c;
        }
    }
    return -1; // 无法到达终点
}
inline int FF()
{
    int ans = 0, c;
    while ((c = dfs()) != -1)
    {
        memset(vis, 0, sizeof(vis));
        ans += c;
    }
    return ans;
}

Edmond-Karp算法

其实，EK算法就是BFS实现的FF算法。

#include<bits/stdc++.h>
//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int  long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 5;
int vis[MAXN], inqueue[MAXN];
int head[MAXN];
int cnt = 2;
int n, m, s, t;
int source, sink;
struct Edge {
    int from, to, w, next;
} edges[MAXN];

void add(int u, int v, int w) {//添加一条边u--v
    edges[cnt].to = v;
    edges[cnt].w = w;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

int last[MAXN], flow[MAXN];

inline int bfs() {
    memset(last, -1, sizeof(last));
    queue<int> q;
    q.push(s);
    flow[s] = inf;
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (p == t) // 到达汇点，结束搜索
            break;
        for (int eg = head[p]; eg; eg = edges[eg].next) {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && last[to] == -1) // 如果残余容量大于0且未访问过（所以last保持在-1）
            {
                last[to] = eg;
                flow[to] = min(flow[p], vol);
                q.push(to);
            }
        }
    }
    return last[t] != -1;
}

inline int EK() {
    int maxflow = 0;
    while (bfs()) {
        maxflow += flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to) // 从汇点原路返回更新残余容量
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
    return maxflow;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);

    }

    print(EK());
}

它的复杂度上限是 $O(ve^2)$ ，其中 v 为点数。

Dinic算法

然而，最常用的网络流算法是Dinic算法。作为FF/EK算法的优化，它选择了先用BFS分层，再用DFS寻找。它的时间复杂度上界是 $O(ev^2)$ 。

#include<bits/stdc++.h>
//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int  long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 5;
int vis[MAXN], inqueue[MAXN];
int head[MAXN];
int cnt = 2;
int n, m, s, t;
int source, sink;
struct Edge {
    int from, to, w, next;
} edges[MAXN];

void add(int u, int v, int w) {//添加一条边u--v
    edges[cnt].to = v;
    edges[cnt].w = w;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

int lv[MAXN], cur[MAXN]; // lv是每个点的层数，cur用于当前弧优化标记增广起点
inline bool bfs() // BFS分层
{
    memset(lv, -1, sizeof(lv));
    lv[s] = 0;
    memcpy(cur, head, sizeof(head)); // 当前弧优化初始化
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        for (int eg = head[p]; eg; eg = edges[eg].next) {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && lv[to] == -1)
                lv[to] = lv[p] + 1, q.push(to);
        }
    }
    return lv[t] != -1; // 如果汇点未访问过说明已经无法达到汇点，此时返回false
}

int dfs(int p = s, int flow = inf) {
    if (p == t)
        return flow;
    int rmn = flow; // 剩余的流量
    for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) // 如果已经没有剩余流量则退出
    {
        cur[p] = eg; // 当前弧优化，更新当前弧
        int to = edges[eg].to, vol = edges[eg].w;
        if (vol > 0 && lv[to] == lv[p] + 1) // 往层数高的方向增广
        {
            int c = dfs(to, min(vol, rmn)); // 尽可能多地传递流量
            rmn -= c; // 剩余流量减少
            edges[eg].w -= c; // 更新残余容量
            edges[eg ^ 1].w += c; // 再次提醒，链式前向星的cnt需要初始化为1（或-1）才能这样求反向边
        }
    }
    return flow - rmn; // 返回传递出去的流量的大小
}

int dinic() {
    int ans = 0;
    while (bfs())
        ans += dfs();
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    print(dinic());
}