网络流笔记

网络流是什么

是网络流是一种类比水流的解决问题方法,与线性规划密切相关。虽然模型简单,但是应用却十分广泛。


Dinic算法

Dinic算法是一种对于网络流问题的增广路算法,它通过对残量网络进行分层,并在层次图上寻找增广路的方式,实现了在$O(n^2m)$的时间内求出网络的最大流。在加入多路增广当前弧优化后,复杂度远小于理论上界。

变量解释

$no[x]$是点$x$的指针

  • $level$:表示层数
  • $fir$:表示邻接表中的第一条边
  • $curr$:当前弧优化,表示目前访问到的边

$Edge*$ 是边指针

  • $next$:表示下一条边
  • $to$:表示指向节点
  • $res$:表示反向边

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Dinic {
public:
int operator() (int s, int t, int n) {
int max_flow = 0;
while (bfs(&no[s], &no[t], n)) {
max_flow += dfs(&no[s], &no[t]);
}
return max_flow;
}
private:
// 建立层次网络
bool bfs(Node *s, Node *t, int n) {
for (int i = 1; i <= n; ++i) {
no[i].level = -1; no[i].curr = no[i].fir;
}
std::queue<Node *> q; s->level = 1; q.push(s);
while (!q.empty()) {
Node *v = q.front(); q.pop();
for (Edge *e = v->fir; e; e = e->next) {
if (e->flow != 0 && e->to->level == -1) {
e->to->level = v->level+1;
if (e->to == t) return true;
q.push(e->to);
}
}
}
return false;
}
// 寻找增广路
int dfs(Node *s, Node *t, int limit = oo) {
if (s == t) return limit;
int cnt_flow = 0;
// cnt_flow 记录已使用的流量,以达到多路增广的效果
for (Edge *&e = s->curr; e; e = e->next) {
// 注意 *&e 这样才能起到当前弧优化的效果
if (e->flow != 0 && e->to->level == s->level+1) {
int flow = dfs(e->to, t, std::min(limit-cnt_flow, e->flow));
cnt_flow += flow; e->flow -= flow; e->res->flow += flow;
if (cnt_flow == limit) return cnt_flow;
}
}
if (cnt_flow != limit) s->level = -1;
// 这是个小优化,至于为什么留给读者自己思考。
return cnt_flow;
}
}dinic;

模板题地址

LYOI


重要结论及模型

记 $ S $ 为源点,$T$为汇点,$c(u,v)$为在点u,v之间的容量。

最大流最小割定理

最大流等于最小割

详细证明请参考《最小割模型在信息学竞赛中的应用》hbt

hbt. 胡伯涛 2007年国家集训队论文《最小割模型在信息学竞赛中的应用》

二分图最大匹配

构图

设二分图\(G=(V_1,V_2,E)\)
$\begin{cases}
c(s,u) = 1,&u\in V_1\
c(u,v)=1,&\langle u,v\rangle\in E\
c(v,t)=1,&v\in V_2\end{cases}$
答案就是最大流

模型理解

这个模型比较好理解,因为每个点的流量至多为1,保证了每个点只能用一次。

方案输出

遍历第二部分的边,如果满流则就是一对匹配。

最大权闭合子图

构图

模型理解

证明比较复杂,详细证明请参考hbt

方案输出

最小割即为方案

最小路径覆盖

构图

将一个点拆成两个点一个表示入,一个表示出,答案就是最大匹配。

上下界网络流

推荐阅读Menci的blog。很详细,对四种情况都进行了讨论。

~感谢投食~