定义

在有向图中，有唯一的源地（入度为 0）和汇点（出度为 0），每一条边都有非负的容量，且整张图都会保证平衡状态。这样的图叫做网络流图。

基本网络流算法

最大流 – Dinic

每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次，再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。

其中值得一提的是，Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针，避免不必要的遍历。

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s), dep[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && dep[edges[i].to] == 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[t] != 0;
}

int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1)
        {
            int di = dfs(edges[i].to, min(flow, edges[i].weight));
            if (di > 0)
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
        }
    return 0;
}

int dinic()
{
    int ans = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(head));
        while (int di = dfs(s, INF))
            ans += di;
    }
    return ans;
}

最小割

删除流量和最小的边集使得 S 与 T 不连通，就叫做最小割。最小割等于最大流。

例题：[USACO2007 OPEN]吃饭 Dining

费用流 – SPFA + DFS

概念：在最大流的情况下求得最小的费用。其实可以直接 SPFA + Dinic 就行了，先找到一条最短路，然后再求该路径上的最大流，然后可以保证最大流的情况下求得最小费用。

bool bfs()
{
    memset(dist, 0x3f, sizeof(dist)), memset(flow, 0x3f, sizeof(flow));
    memset(vis, false, sizeof(vis)), memset(pre, -1, sizeof(pre));
    queue<int> q;
    q.push(st), dist[st] = 0, vis[st] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop(), vis[u] = false;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && dist[edges[i].to] > dist[u] + edges[i].cost)
            {
                dist[edges[i].to] = dist[u] + edges[i].cost;
                pre[edges[i].to] = i, flow[edges[i].to] = min(edges[i].weight, flow[u]);
                if (!vis[edges[i].to])
                    vis[edges[i].to] = true, q.push(edges[i].to);
            }
    }
    return pre[ed] != -1;
}

long long mfmc()
{
    long long tot_cost = 0, tot_flow = 0;
    while (bfs())
    {
        tot_flow += flow[ed], tot_cost += 1LL * flow[ed] * dist[ed];
        int p = ed;
        while (p != st)
        {
            int i = pre[p];
            edges[i].weight -= flow[ed], edges[i ^ 1].weight += flow[ed];
            p = edges[i ^ 1].to;
        }
    }
    return tot_cost;
}

网络流经典模型

最大权闭合子图

例题（来自于网络流 24 题）：https://loj.ac/problem/6001

这一类模型主要就是建立一个依赖关系的有向图，一般分为两个部分：正权部分和负权部分。一般求其权最大的闭合子图。

一篇非常好的博客文章让我快速的理解了这个神仙玩意，大家可以去看一下。这个东西简单来讲就是在原先的基础上加源点和汇点，然后把点权转换成边权，转而求最小割、也就是最大流。如果正权满流了，那么就是要去掉这一个计划；如果是负权满流了，那么就是要在原图中割掉这条边。

题解：LOJ6001:「网络流 24 题」太空飞行计划题解

「等待时间叠加」模型

经典的例题：[SCOI2007]修车

首先，\(n\)个车主可以把整个时间分为\(n\)个时间段，然后每一个时间段的工人其实是不一样的，所以拆成\(n * m\)个点，每个点流经的上界都是\(1\)，且费用都按当前次序乘上权值即可。

相似的题目还有 NOI 美食节一题。

二分图最小点权覆盖

例题：POJ 2125

考虑将一个点拆成两个：一个入点，一个出点。入点和出点分开之后，源点连\(w_-\)的权，汇点连上\(w_+\)的权。当一条边满流，说明走过了中间的入点，亦而反之即可搞定这道题。

// POJ2125.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int MAX_N = 2e5 + 200, INF = 0x3f3f3f3f;

using namespace std;

int n, m, head[MAX_N], current, dep[MAX_N], cur[MAX_N], st, ed;
bool mark[MAX_N];

struct edge
{
    int to, nxt, flow;
} edges[MAX_N << 1];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].flow = weight, head[src] = current++;
}

void addtube(int src, int dst, int flow)
{
    addpath(src, dst, flow);
    addpath(dst, src, 0);
}

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    dep[st] = 1;
    queue<int> q;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].flow > 0 && dep[edges[i].to] == 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[ed] != 0;
}

int dfs(int u, int flw)
{
    if (u == ed || flw == 0)
        return flw;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].flow > 0 && dep[edges[i].to] == dep[u] + 1)
        {
            int di = dfs(edges[i].to, min(flw, edges[i].flow));
            if (di > 0)
            {
                edges[i].flow -= di, edges[i ^ 1].flow += di;
                return di;
            }
        }
    return 0;
}

int dinic()
{
    int ans = 0;
    while (bfs())
    {
        memcpy(cur, head, sizeof(head));
        while (int di = dfs(st, INF))
            ans += di;
    }
    return ans;
}

void dfs_helper(int u)
{
    mark[u] = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].flow > 0 && !mark[edges[i].to])
            dfs_helper(edges[i].to);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m), st = (n << 1) | 1, ed = st + 1;
    for (int i = 1, tmpy; i <= n; i++)
        scanf("%d", &tmpy), addtube(i + n, ed, tmpy);
    for (int i = 1, tmpx; i <= n; i++)
        scanf("%d", &tmpx), addtube(st, i, tmpx);
    for (int i = 1, tmpx, tmpy; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), addtube(tmpx, tmpy + n, INF);
    printf("%d\n", dinic());
    dfs_helper(st);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!mark[i])
            ans++;
    for (int i = n + 1; i <= 2 * n; i++)
        if (mark[i])
            ans++;
    printf("%d\n", ans);
    for (int i = 1; i <= n; i++)
        if (!mark[i])
            printf("%d -\n", i);
    for (int i = n + 1; i <= 2 * n; i++)
        if (mark[i])
            printf("%d +\n", i - n);
    return 0;
}

还有一道相似的题目，不过是带权的，用了相同的思路：P2469 [SDOI2010]星际竞速。在二分图上进行覆盖，然后算出最小代价。

有上下界的网络流

无源汇的上下界可行流

问题描述

给定一个网络，每一条边的流量都要满足在区间\([lower[e_x], upper[e_x]]\)中，求一种可行的流量。

解决方案

考虑把每一条边的区间进行化简，变成\([0, upper[e_x] – lower[e_x]]\)就变成了一个正常的网络流模型了。但是，因为每一条边的下限和上限都有所不同，所以如果直接求最大流，会出现一种情况：某些边满流之后，某些边的下限不够低而导致于题意不符合。所以，我们需要处理一个数组\(di[u]\)，代表需要补充或者是放出的流量，所以可知：

\[ di_u = \sum_{e = E(?, u)} e.flow – \sum_{e = E(u, ?)} e.flow \]

对于\(di_u > 0\)的情况下，考虑将超级源点\(S\)连接到\(u\)，来补充所需要的流量；对于\(di_u < 0\)的情况下，考虑将点\(u\)连至超级汇点，来放出多余的流量。所以，就很显然可以解决了。

有源的上下界可行流

问题描述

给定一个网络，每一条边的流量都要满足在区间\([lower[e_x], upper[e_x]]\)中，且给定源点汇点\(s\)与\(t\)，流入源点的流等于流出汇点的流，求一种可行的流量。

解决方法