网络流入门：最大流、最小割与实际应用场景

网络流是图论中最精彩的部分之一，具有极其广泛的实际应用。

一、基本概念

• 源点 S：流量的起点


• 汇点 T：流量的终点


• 容量 c(u,v)：边 (u,v) 允许通过的最大流量


• 流量 f(u,v)：边 (u,v) 实际通过的流量


• 满足：容量限制、反对称性、流量守恒

1. EK 算法（Edmonds-Karp）

1. Dinic 算法（竞赛首选）

int dinic(int u, int flow) {
       if (u == T) return flow;
       int rest = flow;
       for (int &i = cur[u]; i && rest; i = nxt[i]) {
           if (dep[to[i]] == dep[u] + 1 && cap[i]) {
               int k = dinic(to[i], min(rest, cap[i]));
               if (!k) dep[to[i]] = 0;
               cap[i] -= k, cap[i^1] += k;
               rest -= k;
           }
       }
       return flow - rest;
   }

• 最小割方案：最大流后从 S 出发遍历残量网络


• 最小割求解"二者不可得兼"的最优化问题


• 最大权闭合子图

1. 二分图最大匹配 → 最大流


2. 最小路径覆盖 → 拆点 + 最大流


3. 最大权闭合子图 → 最小割


4. 任务分配问题 → 费用流

• SSP 算法：SPFA + Dinic


• 处理负权边：用势能（Johnson 的思想）

• 最大流：洛谷 P3376（模板）


• 二分图匹配：洛谷 P3386


• 最小割：洛谷 P1344 追查坏牛奶


• 费用流：洛谷 P3381 最小费用最大流