一些普通网络流的知识。

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 最大流最小割定理及其应用

1.3.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.3.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$。

于是最大权闭合子图为 $$正点权之和 - 最小割$$。

$S$ 连正价点，权为点权。负价点连汇，权为负点权。原图有向边保留，权为 $+\infty$。考虑割的意义，割去正权点表示不选该点，割掉负权点表示选择该点。

另外，如果存在流，那么必然存在正不选负选，不是闭合子图，矛盾。

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

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

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

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

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

最小割即所求。

1.3.3 集合划分模型

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.3.4 切糕模型

P3227 [HNOI2013] 切糕

给出 $n\times m\times h$ 的长方体，以及 $V_{x,y,z}$ 和 $D$。对于每个点对 $(x,y)$ 选出 $f_{x,y}\in[1,h]$ 使得 $\vert f(x,y)-f(x’,y’)\vert\le D$，其中 $\vert x-x’\vert+\vert y-y’\vert=1$。最小化 $\sum v_{x,y,f_{x,y}}$。

对每个 $f_{x,y}$ 拆出 $h+1$ 个点 $f_{x,y,1},f_{x,y,2},\cdots,f_{x,y,h+1}$。考虑建边：

$$S\stackrel{+\infty}{\longrightarrow}f_{x,y,1}\par f_{x,y,k}\stackrel{v_{x,y,k}}{\longrightarrow} f_{x,y,k+1}\par f_{x,y,h+1}\stackrel{\infty}{\longrightarrow}T$$

最小割显然是没有 $D$ 的限制下的答案。如何把 $D$ 的限制考虑进去？

也就是使 $f_{x,y}-f_{x’,y’}>D$ 时存在增广路，于是考虑从 $f_{x,y,k}$ 向 $f_{x’,y’,k-D}$ 连边即可。

另外，考虑一条链（就是一对 $(x,y)$）上最多割一条边，连 $f_{x,y,c}\stackrel{+\infty}{\longrightarrow}f_{x,y,c-1}$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

scanf ("%d%d%d%d", &p, &q, &r, &d); T = 100000;
for (int i = 1; i <= r; i ++)
    for (int j = 1; j <= p; j ++)
        for (int k = 1; k <= q; k ++)
            scanf ("%d", &v[i][j][k]);
for (int x = 1; x <= p; x ++)
    for (int y = 1; y <= q; y ++) {
        link (S, getnode (x, y, 1), inf);
        link (getnode (x, y, r + 1), T, inf);
        for (int k = 1; k <= r; k ++) link (getnode (x, y, k), getnode (x, y, k + 1), v[k][x][y]), link (getnode (x, y, k + 1), getnode (x, y, k), inf);
        for (int k = d + 1; k <= r + 1; k ++) {
            for (int sb = 0; sb < 4; sb ++) {
                int dx = x + dir[sb][0], dy = y + dir[sb][1];
                if (dx >= 1 && dx <= p && dy >= 1 && dy <= q) link (getnode (x, y, k), getnode (dx, dy, k - d), inf);
            }
        }
    }

P6054 [RC-02] 开门大吉

$n$ 个选手，$m$ 套题，每套题有 $p$ 道题。第 $i$ 个选手答对第 $j$ 套题的第 $k$ 题的概率为 $f_{i,j,k}$，答对第 $k$ 题的奖励为 $c_k$，只要答错题就停止答题。给第 $i$ 个选手分配第 $u_i$ 套题，满足给出若干条 $(i,j,k)$ 表示 $u_i-u_j\ge k$ 的限制。最小化期望奖励和。

设 $F_{i,j}$ 为离散变量，表示第 $i$ 个选手选第 $j$ 套题。

考虑 P3227 的切糕模型。连边：

1. $S\stackrel{+\infty}{\longrightarrow}F_{i,1}$。
2. $F_{i,j}\stackrel{v_{i,j}}{\longrightarrow}F_{i,j+1}$，对于 $i\in[1,m]$，其中 $v_{i,j}$ 表示第 $i$ 个人做第 $j$ 套题的期望奖励。
3. $F_{i,j+1}\stackrel{v_{i,j}}{\longrightarrow} F_{i,j}$，对于 $i\in[1,m]$。这一连边保证这一条链上只有一个边被割。
4. $F_{i,m+1}\stackrel{\infty}{\longrightarrow} T$。

接下来考虑限制 $(i,j,k)$。即 $u_i\ge u_j+k$。也就是不得出现 $u_i<u_j+k$，连 $F_{j,t}\stackrel{j}{\longrightarrow}F_{j,t+k}$。注意，若 $t+k>m+1$，需要取 $\min$，这样防止了最后的无限制的情况（如果前面写了 3. 的连边，这里可以不连）。

为啥是 $F_{j,t}$ 向 $F_{i,t+k}$ 连边？

注意，最小割中权 $+\infty$ 的边实际上表示一种「蕴含关系」。即 $i\stackrel{+\infty}{\longrightarrow}j$ 表示的是，若 $i\in S\implies j\in S$。在上式中，若 $u_i\ge u_j+k$，则对于所有 $t$，若割 $F_{j,t}$，必然存在 $t’\ge t+k$，使得 $F_{i,t’}$ 被割，显然 $F_{i,t+k}$ 也被割。而反过来显然无法如此约束。

ARC142E Pairing Wizards

给出 $a_i,b_i$。给出 $m$ 条限制 $(i,j)$，$(a_i+c_i\ge b_i\land a_j+c_j\ge b_j)\lor (a_i+c_i\ge b_j\land a_j+c_j\ge b_i)$。给每个 $c_i$ 赋非负权值，使得 $\sum c_i$ 最小。

2. 费用流

2.1 最小费用最大流

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

2.1.1 一般方法

和 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 ();
}

2.1.2 Primal-Dual 原始对偶算法

上面算法的复杂度为 $\mathcal O(nmf)$，而瓶颈在 SPFA 的过程。这是负权边带来的。

考虑 Johnson 求全源最短路的过程，使所有边权非负，然后跑 Dijkstra 从而可以找到费用最小的增广路，即先跑 SPFA，设到 $u$ 的最短路为 $h_u$，对于边 $u\stackrel{w}{\longrightarrow}v$ 新权赋值为 $w+h_u-h_v$ 即可。在跑完一轮重新求之前，将 $h_i$ 更新为 $h_i+dis_i$。具体见 Johnson。

2.1.3 例题

下文 $(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)$ 的边。跑最小费用最大流。

2.2 有上下界的网络流

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

2.2.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;
}

2.2.2 有源汇上下界可行流

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

2.2.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 了。。。

2.2.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;
}

2.2.5 有负环的费用流

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

2.2.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 基本定义

• 图的匹配：选出某些边使得任意两条边没有公共点，选出的边为「匹配边」，匹配边的端点为「匹配点」。

• 点覆盖：选出某些点使得所有边上至少有一个点被选。

• 边覆盖：选出某些边使得所有点至少有一条与其相连的边被选。

• 独立集：选出某些点，使得任意两点都没有边。

• 闭合子图：有向图的一个子图，使得没有指向子图外的出边。

• 路径覆盖：DAG 上边不相交的简单路径覆盖所有节点。

• 增广路：由未匹配点开始，交替经过非匹配边、匹配边，以非匹配点结束的路径。

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

• 二分图判定：充要条件是没有奇环，故可以直接黑白染色判断。

• 二分图最大匹配：二分图中边最多的匹配。可以用 Dinic 直接做，复杂度为 $\mathcal O(m\sqrt n)$。

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}$。连通块的答案为两种颜色点数最小值。求和即为最终答案。

3.2 二分图的定理

设最大匹配数为 $P$，图上点数为 $N$。

最小点覆盖为 $P$

最大匹配中的所有边没有公共点，设有 $P$ 条边，那么至少需要 $P$ 个点才能实现点覆盖。 考虑如何用 $P$ 个点覆盖所有边，尝试从未匹配点（假设为左部点）出发寻找增广路。最大匹配显然不存在完整的增广路。对于能与非匹配边连上的匹配边，选择右部点；反之，选择左部点。这样就构造完毕了。

最小边覆盖为 $N-P$

一条边最多覆盖 $2$ 个点，故优先考虑最大匹配上边，共 $P$ 条，剩余 $N-2P$ 个点。 另外，考虑未匹配的点。由于无法扩充匹配，故每个点对应着一条边，即需要再选 $N-2P$ 条边。 于是为 $P+N-2P=N-P$ 条边为最小边覆盖。

最大独立集为 $N-P$

仍然从最大匹配考虑，剩下的点都能选。故至少是 $N-P$。然后如果选最大匹配内一点，就有匹配了，所以是这个。

Hall 定理

• 二分图完美匹配：设左右部点集分别为 $X,Y$。当匹配数达到 $\min(\vert X\vert,\vert Y\vert)$ 时为完美匹配。
• 邻域：对于 $W\subseteq X$，称 $N_G(W)$ 为 $W$ 在二分图 $G$ 中的邻域，即 $Y$ 中与 $W$ 至少一点有连边的全体顶点集合。形式化的，$N_G(W)={y\in Y\vert\exist x\in S,(x,y)\in E}$。简记为 $N(W)$。

Hall 定理告诉我们如下的充要条件。

不妨设 $\vert X\vert \le \vert Y\vert $

$$二分图存在完美匹配\iff \forall W\subseteq X,\vert W\vert \le \vert N(W)\vert$$

也就是说，对于任意一个左部点的子集，都能被匹配。

考虑最小割。从 $S$ 向 $X$ 连容量为 $1$ 的有向边，从 $Y$ 向 $T$ 连容量为 $1$ 的边。再连原图上 $X,Y$ 的边，容量为 $+\infty$。存在完美匹配，即最大流为 $\vert X\vert$。不存在即最大流小于 $\vert X\vert$。

而最小割=最大流，即最小割 $<\vert X\vert$。考虑求出最小割，显然不能选中间 $\infty$ 的边。假设在割后，一个子集 $W\subseteq X$，为与源点相连的点集。则最小割为 $\vert X\vert-\vert W\vert+\vert N(X)\vert$。当最小割 $<\vert X\vert$ 时，$\vert X\vert-\vert W\vert+\vert N(X)\vert<\vert\longrightarrow \vert N(W)\vert<\vert W\vert$，证毕。

• 推论：二分图最大匹配为 $\vert X\vert -\max (\W-\vert N(W)\vert)$。 其实和上述证明是一样的。

• 多重匹配：加权后，仍然满足。

最小路径覆盖

• 最小路径覆盖=$N-拆点后二分图最大匹配$

每个点的出入点作为一个匹配，那么显然是覆盖了所有点，但是覆盖数为 $N$。尝试减小这个值，将路径上的边以出点向入点连边。左右部点互不相同分别保证了无法扩散、无法会聚。据此一个匹配必然是合法的，另外一个匹配实际上减少了一次覆盖。故最大匹配构造出最小覆盖。

P2764 最小路径覆盖问题 。

最小链覆盖

TBD.