定义
在有向图中，有唯一的源地（入度为 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 不连通，就叫做最小割。最小割等于最大流。
费用流 – 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
这一类模型主要就是建立一个依赖关系的有向图，一般分为两个部分：正权部分和负权部分。一般求其权最大的闭合子图。
一篇非常好的博客文章让我快速的理解了这个神仙玩意，大家可以去看一下。这个东西简单来讲就是在原先的基础上加源点和汇点，然后把点权转换成边权，转而求最小割、也就是最大流。如果正权满流了，那么就是要去掉这一个计划；如果是负权满流了，那么就是要在原图中割掉这条边。
「等待时间叠加」模型
经典的例题：[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\)，流入源点的流等于流出汇点的流，求一种可行的流量。
解决方法