网络流

2025-08-20T19:16:00+08:00 | 11分钟阅读 | 更新于 2025-08-20T19:16:00+08:00

@ Jason Chan

一些普通网络流的知识

1. 网络流

1.1 定义

网络是一张有向图。$c(u,v)$ 为容量限制。如果不存在边 $(u,v)$，则 $c(u,v)=0$

网络可行流：有源汇以及无源汇。

流函数：有序点对 $(u,v)$ 到实数集的映射 $f$，表达的是这条边的最大容积。
容量限制： $f(u,v)\le c(u,v)$。若相等，则称「满流」。
斜对称性：$f(u,v)=-f(v,u)$。
流量守恒：对于所有非源汇点，每个节点流入以及流出的流量相等。
对于 有源汇 网络，有：$\sum f(S,i)=\sum f(i,T)$，称为「流量」。

1.2 最大流

对于给定网络，使得网络流量最大的合法流函数为这个网络的最大流。

残量网络 $G_f=(V,E_f)$ 是 $c_f=c-f$ 的网络。特别的，若 $c_f=0$，那么这条边就不存在。
增广路：残量网路上，源点到汇点的一条路径。

1.2.1 FF 算法

简单的贪心是，每次找一条 $S\to T$ 的路径，使得路径上每条边的剩余流量都不为 $0$。设路径上最小流量为 $mn$，将所有边的剩余流量都减掉 $mn$。如此循环下去，直至任意增广路最小边剩余流量均为 $0$。

很遗憾，这个贪心是错误的。

考虑反悔贪心的思想，我们在 $(u,v)$ 流过 $f$ 的流量时，令 $c(v,u)\gets c(v,u)+f$，之后继续增广即可。

这种算法为 Ford-Fulkerson 算法，最坏复杂度为 $\mathcal O(mf)$。

1.2.2 EK 算法

实际上只需将 FF 算法中"找一条增广路"改为“找一条长度最短的增广路”即为 EK 算法。时间复杂度为 $\mathcal O(nm^2)$，跑不满。

1.2.3 Dinic 算法

在 EK 算法上稍作改动，由于可能有多条最短路径，我们可以一次性将其全部增广。就能得到 Dinic 算法。

具体而言，我们先 BFS 一遍求出 $S$ 到所有点的深度 $dep_u$，将图分层。考虑所有 $dep_v=dep_u+1$ 的边 $(u,v)$，从 $S$ 携带 $+\infin$ 流递归。枚举所有邻居，尽量将目前的流发给邻居并递归下去。递归结束后更新当前流。

若流为 $0$ 或者访问结束，返回即可。若到达 $T$，则直接把当前流送出去即可。

由于 $dep$ 的递增性，我们有效边构成的子图必然是 DAG。因此我们至多会访问任意一边一次。类比欧拉回路，进行「当前弧优化」。

当前弧优化的 Dinic 复杂度为 $\mathcal O(n^2m)$，也跑不满。

 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


bool getDep () {
    queue <int> q; memset (dep, 0, sizeof dep);
    q.push (s); now[s] = head[s]; dep[s] = 1; 
    while (!q.empty ()) {
        int u = q.front (); q.pop ();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v; ll c = e[i].c;
            if (!dep[v] && c) now[v] = head[v], dep[v] = dep[u] + 1, q.push (v); 
        }
    }
    return dep[t];
}

ll getFlow (int u, ll flow) {
    if (u == t) return flow; ll ret = 0;
    for (int i = now[u]; i; i = e[i].nxt) {
        now[u] = i;
        int v = e[i].v; ll c = e[i].c;
        if (dep[v] == dep[u] + 1 && c) {
            ll res = getFlow (v, min (flow - ret, c));
            e[i].c -= res; e[i ^ 1].c += res;
            ret += res;
            if (ret == flow) return flow; 
        }
    }
    return ret;
}

ll dinic () {
    ll ret = 0;
    while (getDep ()) ret += getFlow (s, inf);
    return ret;
}

当前弧优化不可写成如下这样：

1

for (int& i = now[u]; i; i = e[i].nxt)

必须要写成：

1
2
3
4


for (int i = now[u]; i; i = e[i].nxt) {
    now[u] = i;
    // ...
}

这是由于错误写法会在流未满跳过边，导致表现甚至劣于 EK。

1.3 最小费用最大流

定义费用函数：对于 $(u,v)\in E$，定义 $w(u,v)$ 为费用函数，要求其在满足最大流的前提下，最小化 $\sum f(u,v)\cdot w(u,v)$。

和 EK 优化的思路同样，我们只需将增广最短路径更改为增广费用最小路径即可。反向边相当于退流，因此 $e$ 的反向边费用为 $e$ 的负值。

存在负权边，因此应用 SPFA。

EK 求最小费用最大流的时间复杂度上界为 $\mathcal O(nmf)$。这是 OI 中最常用求费用流的方法。故有俗语「最大流不卡 Dinic，费用流不卡 EK」。

 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


bool SPFA () {
    queue <int> q; for (int i = 1; i <= n; i ++) vis[i] = false, dis[i] = inf, now[i] = head[i];
    q.push (S); dis[S] = 0; vis[S] = true;
    while (!q.empty ()) {
        int u = q.front (); q.pop ();
        vis[u] = false;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v; ll c = e[i].c, w = e[i].w;
            if (c && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) q.push (v), vis[v] = true; 
            }
        }
    }
    return dis[T] != inf;
}

ll getCost (int u, ll flow) {
    if (u == T) return flow;
    vis[u] = true;
    ll ret = 0;
    for (int i = now[u]; i && flow; i = e[i].nxt) {
        now[u] = i;
        int v = e[i].v; ll c = e[i].c, w = e[i].w;
        if (!vis[v] && c && dis[v] == dis[u] + w) {
            ll res = getCost (v, min (flow, c));
            if (!res) dis[v] = inf;
            e[i].c -= res;
            e[i ^ 1].c += res;
            flow -= res;
            ret += res;
            cost += res * w;
        }
    }
    vis[u] = false;
    return ret;
}

ll work () {
    ll ret = 0;
    while (SPFA ()) ret += getCost (S, inf);
    return ret;
}

啊啊这个是 Dinic 啊。由于递归的常数较大，因此在最小费用最大流中表现是不如 EK 的，下面是一份 EK 的代码。

 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


bool SPFA () {
    queue <int> q;
    for (int i = s; i <= t; i ++) vis[i] = false, f[i] = k, dis[i] = -inf, pre[i] = -1;
    q.push (s); vis[s] = 1; dis[s] = 0;
    ++ cnt;
    while (!q.empty ()) {
        int u = q.front (); q.pop ();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v, c = e[i].c, w = e[i].w;
            if (c && dis[v] < dis[u] + w) {
                dis[v] = dis[u] + w;
                pre[v] = i;
                f[v] = min (f[u], c);
                if (!vis[v]) vis[v] = true, q.push (v);
            }
        }
    }
    return dis[t] != -inf;
}

int getFlow () 
    flow += f[t];
    int x = t;
    cost += dis[t] * f[t];
    while (x != s) {
        int id = pre[x];
        e[id].c -= f[t];
        e[id ^ 1].c += f[t];
        x = e[id].u;
    }
    return cost;
}

void EK () {
    while (SPFA ()) getFlow ();
}

1.3.2 例题

下文 $(u,v)$ 表示流量为 $u$，费用为 $v$ 的边。

P2045 方格取数加强版

考虑拆点。将所有点 $(x,y)$ 拆成 $in_{x,y}$ 以及 $out_{x,y}$。入点向对应的出点连 $c=1,w=a_{x,y}$ 以及 $c=k-1,w=0$ 的边。$out_{x,y}$ 向 $in_{x+1,y}$ 与 $in_{x,y+1}$ 连 $c=k,w=0$ 的边。跑最大费用最大流即可。

CF277E Binary Tree on Plane

我们考虑用流量来限制每个点的父亲数以及儿子数。

若 $y_u>y_v$，那么从 $u$ 向 $v$ 连一条 $(1,\operatorname{dis}(u,v))$ 的边。这样做会导致逻辑混乱。

考虑拆点。$u_1$ 表示 $u$ 作为父亲时的点，$u_2$ 表示 $u$ 作为儿子时的点。

从 $S$ 向每一个 $u_1$ 连 $(2,0)$ 的边，表示至多有两个儿子。

从每一个 $u_2$ 向 $T$ 连 $(1,0)$ 的边，表示至多有一个父亲。

最后跑最小费用最大流即可。min-cost-max flow.

P3358 最长k可重区间集问题

选给定开区间，使得数轴上任意点被所选区间覆盖不超过 $k$ 次，开区间长度最大。

这个问题实际上可以看做在数轴上从选不重区间。设从原点开始选直到选不了为一轮，选 $k$ 论。

这样，我们就有建图思路：

对于所有 $i$，建边 $i\to i+1:(k,0)$。
对于所有给定开区间 $(l,r)$，建边 $l\to r:(1,len)$

跑 max-cost-max-flow 即可。

CF863F Almost Permutation

构造长度为 $n\le 50$ 的值域为 $[1,n]$ 的序列 $a$，给出 $q\le100$ 个限制，每个限制限定了给定区间内数的范围。设 $i$ 在 $a$ 中出现次数为 $cnt_i$，最小化 $\sum cnt_i^2$。

首先我们对于每个 $i$，暴力求出 $a_i$ 的取值范围 $[l_i,r_i]$。从位置点 $i$ 向区间内所有权值点连 $(1,0)$ 的边，这限制了每个位置仅能选一个权值。

考虑对平方的处理。注意到 $i^2=\sum\limits_{j=1}^{i}(2j-1)$。

因此我们对于每个权值点，拆为入点与出点。入点向出点连 $n$ 条边，第 $i$ 条边为 $(1,2i-1)$。这样，若选了当前权值 $k$ 次，费用即为 $\sum\limits_{j=1}^k(2j-1)=k^2$，正是题目所求的。

最后从源点向每个位置点连 $(1,0)$ 的边，每个权值出点向汇点连 $(n,0)$ 的边，跑最小费用最大流即可。

P4249 [WC2007] 剪刀石头布

给定一张确定了 $m$ 条边方向的竞赛图，给剩余边定向，最大化三元环个数。

对于一个三元组，当且仅当存在一个点出度为 $2$ 时，无法构成三元环。也就是说，若第 $i$ 个点的出度为 $deg_i$，那么必然存在 $deg_i\choose 2$ 组 $(u,v)$，使得不成环，这是充要的。

因此，我们正难则反。共有 ${n\choose 3}=\frac{n(n-1)(n-2)}{6}$ 三元组，可以成环的个数为 $\frac{n(n-1)(n-2)}6-\sum\frac{deg_i(deg_i-1)}2=\frac{n(n-1)(n-2)}6-\frac12\sum deg_i^2+\frac{n(n-1)}2$。

现在目标就是最小化 $\sum deg_i^2$。

把所有未定向的边看作点，连向竞赛图中这条边两端的点，为 $(1,0)$。每个竞赛图中点向汇点连 $n$ 条 $(i,2i-1)$ 的边。跑最小费用最大流。

1.4 最大流最小割定理及其应用

1.4.1 最大流最小割定理

割：若删除网络中一组边集 $V$，使点集划分成两个互不相交的集合 $A,B$，且 $S\in A,T\in B$，则 $V$ 即为网络的一个「割集」，简称「割」。割的容量为 $\sum\limits_{u\in A}\sum\limits_{v\in B}c(u,v)$，流量为 $\sum\limits_{u\in A}\sum\limits_{v\in B}f(u,v)$。若 $u,v$ 所在点集不同，那么 $(u,v)$ 为「割边」。
最小割：所有割中容量最小的割。

定理内容：最大流等于最小割。

感性理解一下，根据割的定义，$S$ 与 $T$ 被一组割集划分，必然需要通过这组割集才能连通 $S$ 与 $T$。最小割就是最小的割集，而最大流必然经过这一割集，且上限即为割集。因此最大流等于最小割。

1.4.2 最大权闭合子图

给出有向图 $G=(V,E)$，点有点权，可正可负。求 $V’\subset V$，使得 $\forall u\in V’,(u,v)\in E$，都有 $v\in V’$，最大化 $\sum\limits_{u\in V’}w_u$。

1.4.3 例题

P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

一个人投赞成票与 $S$ 相连，反对票与 $T$ 相连。考虑最小割。

对于本意赞成者，与 $S$ 相连，容量为 $1$。反之亦然。称此类为“Ⅰ 边”

对于朋友 $(x,y)$，我们连容量为 $1$ 的双向边。称此类为“Ⅱ 边”。

那么一组割的，就是将小朋友的意见分成两组。一侧的小朋友要么是通过Ⅰ边与 $S$ 相连，要么是通过 Ⅱ 边与 $S$ 相连。割权的意义就是改变以及不变的代价和。

最小割即所求。

P4313 文理分科

同样的，我们将文科者与 $S$ 相连，容量为 $art_{i,j}$。理科者与 $T$ 相连，容量为 $sci_{i,j}$。

假设全选，即答案为 $\sum (art_{i,j}+sci_{i,j}+sart_{i,j}+ssci_{i,j})$，这显然不合法。考虑继续构造网络关系，通过容斥求解。

我们把 $(i,j)$ 及其周围四个点尝试”缩点“为 $u_1$ 以及 $u_2$。建立容量为 $sart_{i,j}$ 的边 $S\to u_1$，从 $u_1$ 向 $(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)$ 建立容量为 $+\infty$ 的边。并类似的建立容量为 $ssci_{i,j}$ 的边 $u_2\to T$，从 $(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)$ 向 $u_2$ 建立容量为 $+\infty$ 的边。这样操作，一组割必然不能选中容量为 $+\infty$ 的边，这就捆绑了这种相邻关系。最小割出的方案也必然合法，含义为划分成两组集合的最小代价。容斥处理即可。

1.5 有上下界的网络流

就是对于边 $x\to y$ 加上限定条件 $b$：$b(x,y)\le f(x,y)\le c(x,y)$。

1.5.1 无源汇上下界可行流

一个简单的想法是，先让边流上 $b(x,y)$，容量变为 $c(x,y)-b(x,y)$。这样不满足流量守恒。

考虑新建超级源汇点。令 $in_x=\sum\limits_{(y,x)\in E}b(y,x)$，$out_x=\sum\limits_{(x,y)\in E}b(x,y)$。对于所有 $in_x>out_x$ 者，从 $SS$ 向 $x$ 连一条 $in_x-out_x$ 的边，说明可以向外再流 $in_x-out_x$。反之，向 $TT$ 连边即可。最后再和上文一样，对于每条 $(u,v)\in E$，连一条 $c(x,y)-b(x,y)$ 的边。很容易证明这是正确的，因为若不满流，则必然无解。

加上费用流也同理，只需改为 $b(x,y)\times w(x,y)$。

事实上，在代码实现时，可以直接跑 Dinic 在建完边后。

无源汇有上下界可行流

 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


int main (void) {
    scanf ("%d%d", &n, &m); ss = 0, tt = n + 1;
    for (int i = 1; i <= m; i ++) {
        int u, v, l, r;
        scanf ("%d%d%d%d", &u, &v, &l, &r);
        link (u, v, r - l);
        in[v] += l; out[u] += l;
        ::r[i] = r, ::l[i] = l;
    }
    for (int i = 1; i <= n; i ++) {
        if (in[i] > out[i]) link (ss, i, in[i] - out[i]);
        else if (in[i] < out[i]) link (i, tt, out[i] - in[i]);
    }

    dinic ();
    
    bool flag = true;
    for (int i = 1; i <= n; i ++) 
        if (e[m * 2 + i * 2].w) flag = false;

    if (!flag) return puts ("NO"), 0;
    puts ("YES"); 
    for (int i = 1; i <= m; i ++) printf ("%d\n", r[i] - e[i << 1].w);
    return 0;
}

1.5.2 有源汇上下界可行流

将 $T$ 与 $S$ 连一条 $+\infty$ 的边，对于所有点都流量守恒，转化为无源汇上下界可行流了。

1.5.3 有源汇上下界最大流

先跑一个可行流，把 $T\to S$ 新建的 $+\infty$ 边删去，再撤销 $SS$ 与 $TT$，得到残余网络 $G’$。

接下来，以 $S$ 为源在 $G’$ 上向 $T$ 跑最大流，再和可行流的流相加即所求。

有源汇有上下界最大流

 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



int main (void) {

    scanf ("%d%d%d%d", &n, &m, &s, &t); ss = 0, tt = n + 1;
    for (int i = 1; i <= m; i ++) {
        int u, v, l, r;
        scanf ("%d%d%d%d", &u, &v, &l, &r);
        link (u, v, r - l);
        in[v] += l; out[u] += l;
        ::r[i] = r, ::l[i] = l;
    } link (t, s, inf);
    for (int i = 1; i <= n; i ++) {
        if (in[i] > out[i]) link (ss, i, in[i] - out[i]);
        else if (in[i] < out[i]) link (i, tt, out[i] - in[i]);
    }
	dinic ();
    
    bool flag = true;
    for (int i = head[ss]; i; i = e[i].nxt) if (e[i].w) flag = false;

    if (!flag) return puts ("please go home to sleep"), 0;

    for (int i = head[t]; i; i = e[i].nxt)
        if (e[i].v == s) {
            ans = e[i ^ 1].w;
            e[i].w = e[i ^ 1].w = 0;
        }
    ss = s, tt = t;
    printf ("%d\n", ans + dinic ());

    return 0;
}

插一句，loj 的数据水成啥样了，在找第一次流量大小时误从超级汇点枚举，竟然 AC 了。。。

1.5.4 有源汇上下界最小流

$S\to T$ 的最小流是 $T\to S$ 的最大流的相反数。

那么只需将可行流减去 $T\to S$ 的最大流即可。

有源汇有上下界最小流

 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




int main (void) {

    scanf ("%d%d%d%d", &n, &m, &s, &t); ss = 0, tt = n + 1;
    for (int i = 1; i <= m; i ++) {
        int u, v, l, r;
        scanf ("%d%d%d%d", &u, &v, &l, &r);
        link (u, v, r - l);
        in[v] += l; out[u] += l;
    } link (t, s, inf);
    for (int i = 1; i <= n; i ++) {
        if (in[i] > out[i]) link (ss, i, in[i] - out[i]);
        else if (in[i] < out[i]) link (i, tt, out[i] - in[i]);
    }

    dinic ();

    bool flag = true;
    for (int i = head[ss]; i; i = e[i].nxt) if (e[i].w) flag = false;

    if (!flag) return puts ("please go home to sleep"), 0;

    for (int i = head[t]; i; i = e[i].nxt)
        if (e[i].v == s) {
            ans = e[i ^ 1].w;
            e[i].w = e[i ^ 1].w = 0;
        }
    ss = t, tt = s;
    printf ("%lld\n", ans - dinic ());

    return 0;
}

1.5.5 有负环的费用流

我们先强制使负边满流，也就是下界 $b(x,y)=c(x,y)$。再加入 $y\to x$，且 $b(y,x)=0,c(y,x)=c(x,y)$，费用为 $-w(x,y)$。然后跑最大流即可。

1.5.6 例题

下文中 $(u,v)$ 表示下界为 $u$，上界为 $v$。

P4843 清理雪道

从 $S$ 向所有 $i$ 连 $(0,+\infty)$，从 $i$ 向 $T$ 连 $(0,+\infty)$ 的边。对于 DAG 上的边，连 $(1,+\infty)$ 的边。

接下来将有源汇转化为无源汇，跑最小流即可。

另解：二分图。把每个点拆为左右点，对于原图上的 $u\to v$，连 $u_左\to v_右$。答案即为 $n$ 与最大匹配之差。证明？考虑最劣情况是选 $n$ 次，只要匹配一次，就可以减少一次选择。故答案如此。

3. 二分图问题

3.1 基本定义

当 $G=(V,E)$ 的 $V$ 可以分成两个不想交的集合 $A$、$B$ 且任意 $e\in E$ 都连接 $A$ 与 $B$ 时，$G$ 称作「二分图」。

3.2 二分图判定

根据定义，我们可以将 $A$、$B$ 集合中的点染色，不妨使 $A$ 为黑色，$B$ 为白色。那么在遍历的过程中，只要发现相邻点如果有同色，那么必然不是二分图。

当然，如果图中存在奇环，一定不是二分图。

3.2.1 染色法的一个应用 P3430 [POI 2005] DWU-Double-row

若 $u,v$ 相同且在同一行上，那么连接各自所在列，权值为 $1$，表示这两列最终状态不同（一个交换，一个不交换）；若 $u,v$ 相同且在两行，那么连接各自所在列，权值为 $0$，表示这两列最终状态相同（同时交换或者都不交换）。那么我们对于每个连通块，跑一遍二分图染色。对于边 $u\to v$，$col_v=col_u\operatorname{XOR}w_{u\to v}$。连通块的答案为两种颜色点数最小值。求和即为最终答案。