第 4 章 · 02 网络流难点精讲 ★(对应 docs/graph/flow/)

第 4 章 · 02 网络流难点精讲 ★(对应 docs/graph/flow/)

本节定位:对应 OI Wiki docs/graph/flow/(网络流)。难度:进阶难点(★)。前置依赖:本章 01 节(图论基础)+ 第 2 章(BFS/DFS/复杂度)。

⚠️ 注意:网络流是图论里最抽象的一块。难不在算法代码,而在建模——怎么把题目"翻译"成流网络。很多人背得下 Dinic 代码,但看到题目不知道建几条边、怎么设源汇。本节慢节奏讲透算法和建模两条线。

为什么难

算法层面:

1. Dinic 理解难:分层图(BFS)+ 多路增广(DFS)+ 当前弧优化,三件事叠在一起,初学容易懵。
2. 当前弧优化反直觉:DFS 增广时为什么"每条边只走一次不回头"?这违反一般 DFS 的直觉。
3. 反向边的角色:为什么建流的同时要建一条反向边?它如何实现"反悔"?

建模层面:

4. 抽象度高:题目不会直接说"这是个最大流",要你从"二分图匹配""选与不选""割"等表面信息识别出网络流模型。
5. 技巧多:超级源汇、拆点、容量设计、单位容量等套路,不积累就想不到。

慢节奏精讲 · 网络流 docs/graph/flow/max-flow.md

核心概念:最大流 = 最小割

流网络:有源点 s、汇点 t、每条边有容量 c(u,v)。一个"流"是给每条边分配一个流量 f(u,v) \le c(u,v),满足:

1. 容量限制:0 \le f(u,v) \le c(u,v)。
2. 流量守恒:除 s,t 外,每个点流入 = 流出。

最大流:从 s 能送多少流量到 t。

割:把点集分成 S 和 T 两部分,s \in S,t \in T。割的容量是所有从 S 到 T 的边容量之和。最小割就是容量最小的割。

最大流最小割定理:最大流 = 最小割。这是网络流的基石,docs/graph/flow/min-cut.md 有证明。很多建模题(选与不选、收益取舍)本质是求最小割。

FF 方法与反向边

Ford-Fulkerson(FF)方法:只要存在从 s 到 t 的"增广路"(每条边都有剩余容量),就沿着它增广(增加流量)。重复直到没有增广路。

反向边:增广一条边 (u,v) 时,同时给它的反向边 (v,u) 增加容量。这就是"撤销"机制——如果之前走错了,后面可以通过反向边把流量"退回来"。

struct Edge{ int to, cap; };          // 链式前向星,边成对存
vector<Edge> e; vector<int> head, nxt;
void add(int u,int v,int c){          // 加边:正向 + 反向(容量0)成对
  e.push_back({v,c}); nxt.push_back(head[u]); head[u]=e.size()-1;
  e.push_back({u,0}); nxt.push_back(head[v]); head[v]=e.size()-1;
}
​

注意:正反边成对存储,所以边 i 的反向边是 i \oplus 1。这是网络流代码的关键技巧。

EK 算法(BFS 找最短增广路)

Edmonds-Karp:每次用 BFS 找最短增广路(边数最少)。O(V E^2)。

BFS 保证找到的是最短增广路,避免 FF 在某些图上不收敛。EK 简单但慢,Dinic 是它的加强版。

★★★ Dinic 算法(分层图 + 多路增广 + 当前弧优化)

Dinic 是竞赛主流,O(V^2 E),单位容量图 O(E\sqrt V)。三个核心:

1. 分层图(BFS):从 s 做 BFS,给每个点标"到 s 的层数"。DFS 时只能从第 d 层走到第 d+1 层。这保证增广路是最短的,且一次 BFS 后能找很多条。

2. 多路增广(DFS):一次 DFS 里,只要还能走就走,走到 t 就增广一条路,回来继续从同一层找下一条,而不是回到 s 重新 DFS。这大大减少 BFS 次数。

3. 当前弧优化:DFS 到某个点时,记住上次走到哪条边了(cur[u]),下次再 DFS 到这个点时从上次的位置继续,不重头扫。理由:之前走过的边要么已经满,要么走不通了,不用再看。

int d[N], cur[N];                     // d: 层数;cur: 当前弧
bool bfs(){                           // 分层
  memset(d,0,sizeof d); d[s]=1;
  queue<int> q; q.push(s);
  while(!q.empty()){
    int u=q.front(); q.pop();
    for(int i=head[u]; ~i; i=nxt[i]){
      int v=e[i].to;
      if(!d[v] && e[i].cap){
        d[v]=d[u]+1; q.push(v);
      }
    }
  }
  return d[t];
}
int dfs(int u,int lim){               // 多路增广
  if(u==t) return lim;
  int flow=0;
  for(int &i=cur[u]; ~i; i=nxt[i]){   // ★ 当前弧:引用,自动推进
    int v=e[i].to;
    if(d[v]==d[u]+1 && e[i].cap){
      int f=dfs(v, min(lim, e[i].cap));
      if(!f) continue;
      e[i].cap-=f; e[i^1].cap+=f;     // 正向减,反向加
      flow+=f; lim-=f;
      if(!lim) break;
    }
  }
  return flow;
}
int dinic(){
  int maxf=0;
  while(bfs()){ memcpy(cur,head,sizeof cur); maxf+=dfs(s,INF); }
  return maxf;
}
​

💡 学习提示:for(int &i=cur[u]; ...) 里的引用是当前弧优化的精髓。i 推进时 cur[u] 跟着推进,下次 DFS 到 u 直接从上次的位置继续。这个引用是 C++ 特性,改成 int i=cur[u]; 就失效了——必须用引用。漏掉当前弧优化,Dinic 退化到 O(VE^2) 级别。

费用流 MCMF

docs/graph/flow/min-cost.md。在最大流基础上,每条边还有单位费用。求"最大流基础上的最小费用"或"指定流量的最小费用"。

把 Dinic 的 BFS 分层换成 SPFA 找最短(费用)增广路(因为有负权——反向边费用是负的),DFS 多路增广不变。叫 SSP(Successive Shortest Path)算法。

// 把 dinic 里的 bfs 换成 spfa(基于费用),其余结构相同
bool spfa(){                          // 基于 SPFA 找费用最短增广路
  memset(d,0x3f,sizeof d); d[s]=0;
  // ... SPFA 流程,记录前驱边
  return d[t]<INF;
}
​

二分图匹配

docs/graph/graph-matching/(图匹配子目录)。

二分图最大匹配 = 最大流:左边点连超级源 s(容量 1),右边点连超级汇 t(容量 1),原图边容量 \infty 或 1。跑最大流就是最大匹配。

匈牙利算法 docs/graph/graph-matching/bigraph-match.md:O(VE),比最大流建模更简单,二分图匹配首选。核心:对每个左点 DFS 找"增广路"(可调整的匹配),找到就匹配数 +1。

bool dfs(int u){                      // 匈牙利:给 u 找匹配
  for(int v:g[u])
    if(!vis[v]){
      vis[v]=1;
      if(!match[v] || dfs(match[v])){ // v 未匹配,或原匹配能腾出
        match[v]=u; return true;
      }
    }
  return false;
}
​

KM 算法 docs/graph/graph-matching/bigraph-weight-match.md:带权二分图匹配,O(V^3)。

网络流建模技巧

建模是网络流最难的部分,几个常见套路:

1. 超级源点 / 超级汇点:多个起点(终点)时,建一个虚拟的 s(或 t),连容量 \infty 的边到所有真实起点。

2. 拆点限制点容量:点的"经过次数"有限制时,把点 u 拆成 u_{in} 和 u_{out},中间连一条容量 = 点容量 的边。所有入边连 u_{in},出边从 u_{out} 出。

3. 二分图模型:题目有"两类东西配对""选或不选""每行每列只能一个"等约束,往往能建成二分图匹配。

4. 最小割建模:题目说"选 A 就不能选 B""收益取舍""代价最小",常是求最小割。每条 S \to T 的割对应一种决策。

5. 上下界网络流 docs/graph/flow/bound.md:边的流量有下界和上界,需要转化。这是网络流的进阶部分。

💡 学习提示:网络流建模靠积累。刷 20-30 道经典题(洛谷网络流题单)后,模式就熟了。建议先从"明显的最大流"题(如 P3376 模板、P2740 草地排水)起步,再进"需要建模"题(如 P2763 试题库、P2765 魔术球)。

常见误区

⚠️ 注意:

1. 忘建反向边:add(u,v,c) 时如果只加正向边,算法无法"反悔",答案错。必须正反成对存,反向边初始容量 0。
2. 反向边索引错:边 i 的反向边是 i \oplus 1,前提是成对存储且从偶数下标开始(或从 0 开始成对加)。如果边编号从 1 开始,反向边是 i \oplus 1 会错位,常见做法是边编号从 0 开始,或用 i + (i \& 1 ? -1 : 1)。
3. 当前弧优化写错:for(int i=cur[u]; ...) 而不是 for(int &i=cur[u]; ...,漏引用就失效。每次 BFS 后要 memcpy(cur, head, ...) 重置。
4. Dinic 分层条件错:if(d[v]==d[u]+1 && cap) 漏 d[v]==d[u]+1 会乱走,漏 cap 会走满边。
5. 多路增广忘传剩余 lim:DFS 里 lim 是当前路还能承载的流量,递归要传 min(lim, e[i].cap),否则流量算错。
6. 费用流用 Dijkstra 找增广路:有负权(反向边),必须用 SPFA,或用势函数改造的 Dijkstra。
7. 匈牙利忘清 vis 数组:每次给新左点找匹配前要 memset(vis,0,...)。

练习建议

最大流:

• 洛谷 P3376 【模板】网络最大流(Dinic 必背模板)
• 洛谷 P2740 草地排水(最大流入门)
• 洛谷 P2763 试题库问题(二分图建模)
• 洛谷 P2765 魔术球问题(最小路径覆盖建模)

费用流:

• 洛谷 P3381 【模板】最小费用最大流(MCMF 必背)
• 洛谷 P1251 餐巾计划问题(拆点建模)
• 洛谷 P4013 数字梯形问题(费用流建模)

二分图匹配:

• 洛谷 P3386 【模板】二分图匹配(匈牙利必背)
• 洛谷 P1640 [SCOI2010]连续攻击游戏(二分图匹配)

💡 学习提示:网络流模板(Dinic / MCMF / 匈牙利)必须背到默写。比赛时网络流题时间紧,现写代码容易错。建议:模板背熟 → 刷 10 道明显建模题 → 再刷 10 道需要识别模型的题。建模能力是刷出来的,不是看出来的。

本节要点

1. 核心:最大流 = 最小割(网络流基石)。流网络 = 容量限制 + 流量守恒。
2. 反向边:正反成对存储,边 i 的反向边是 i \oplus 1;反向边实现"反悔撤销"。
3. ★★★ Dinic 三件套:BFS 分层 + DFS 多路增广 + 当前弧优化(for(int &i=cur[u];...) 引用),复杂度 O(V^2 E)。
4. 费用流 MCMF:Dinic 的 BFS 换 SPFA(因为有负权);二分图匹配首选匈牙利 O(VE)。
5. 建模技巧:超级源汇、拆点限点容量、二分图模型、最小割决策;靠刷 20-30 道经典题积累。