网络流基本手段

网络流基本概念

我们可以将网络流类比为一些单向通水的水管组成的网络。以下的概念都将这样类比。

• 节点 v： 水管的交点 (交点没有流量限制)。英文 vertex 的首字母。
• 弧 e： 水管 (具有流量限制)。英文 edge 的首字母。
• 容量 c(u,v)： 水管的最大流速。英文 capacity 的首字母。
• 流量 f(u,v)： 水管当前的流速。英文 flow 的首字母。
• 流 F(S,T)： 水管网络仅从 S 进水，从 T 出水，的一个合理的流量方案。

下面，我们又有几个公理：

• 弧的流量限制：$f(u,v)\leq c(u,v)$。
• 流量平衡：节点 v 的进入流量等于流出流量。

然后根据这些概念，我们可以定义网络流中最重要的一个部分：

• 最大流 F(S,T)：：所有流 F(S,T) 中 S 处流速最大的方案。

同时还有几个比较重要的概念：

• 增广路 P(S,T)：指从 S 到 T 的一条经过的弧全部满足 $f < c$的路径。
• 残量网络 G：将原图每条边的 c 减去 f 得到的图。即原图没有满流的边组成的图。

dinic 算法及其优化

dinic 算法是求解网络流问题的重要手段之一。基本地，它可以在最坏 $O(n^2m)$的时间复杂度内求解一幅有向图内从 S 到 T 的最大流。当然，根据不同图的不同特性，这个时间复杂度往往达不到最坏，故我们可以在数据范围不是很大的情况下放心使用 dinic 算法。

dinic 算法的基本步骤是：

• 1. 根据还有剩余流量的边生成分层网络
• 2. 重复这一个步骤：获取可行増广路，并把増广路上的边的流量同时增加到最大可行值。

重复这两个步骤，直到无法生成使 ST 联通的分层网络为止。这时的网络上的流量就是最大流的流量。
但是需要注意的是，为了保证 dinic 算法的正确性，我们在增广时需要将反向边的剩余流量对称的增加，以便算法以后的反悔。
对 dinic 的具体实现不多做介绍，下面着重介绍两个较为有效的优化。

当前弧优化：记录 dinic 算法在每一个节点尝试继续增广时增广到了哪一条边。

整体流量优化：对于每一个节点，记录可以向下流的总流量再返回。这样可以减少递归的次数。

int dep[MX],q[MX];          //分层网络的深度，bfs 的队列
int bfs(int frm,int to)     //生成分层网络
{
    int h=0,t=1,x,y;
    memset(dep,0xff,sizeof(dep));
    q[++h]=frm;
    dep[frm]=0;
    while(h>=t)
    {
        x=q[t++];
        for(int i=fst[x];i!=-1;i=nxt[i])
        {
            y=e[i].v;
            if(dep[y]==-1&&e[i].c)
            {
                dep[y]=dep[x]+1;
                q[++h]=y;
            }
        }
    }
    return (dep[to]>=0);    //返回分层网络是否成功生成
}

int cur[MX];                //当前弧优化的记录数组
int dinic(int x,int mn)
{
    if(x==T)return mn;
    int y,a,now=0;
    for(int &i=cur[x];i!=-1;i=nxt[i])   //"int &i="这一句是当前弧优化的核心
    {
        y=e[i].v;
        if(e[i].c&&dep[y]==dep[x]+1)
        {
            a=dinic(y,min(mn-now,e[i].c));
            now+=a;                     //整体流量优化，记录当前节点往下流的最大流量后再返回
            e[i].c-=a,e[i^1].c+=a;      //帮助 dinic 反悔
            if(mn==now)return now;
        }
    }
    return now;
}

int mxflow()
{
    int tot=0;
    while(bfs(S,T))
    {
        memmove(cur,fst,sizeof(fst));
        tot+=dinic(S,+oo);
    }
    return tot;
}

网络流问题

(Level 1)

1. 单源单汇最大流

直接运用 dinic 算法即可。

2. 多源多汇最大流

建立新的源点 S 和汇点 T，S 与原图的 S 相连，原图的 T 与 T 相连即可。这样就用单源汇网络流代替了多源汇网络流。这种在图的构造上做文章的例子非常多见，而且也是非常有效、常用、深奥的学问。

3. 二分图的最大匹配

即求解二分图两部分间最多有几条不共点的边相连。
将二分图左右两部分间的边容量设为 1，求解从左到右的最大流即可。

(Level 2)

1. 有上下界网络流：

a. 有上下界最大流

如果一条边的流量只能在 [a,b] 的范围内，我们也可以通过对图的修改将这个问题转化为普通的上界网络流。

分析一条边的流量 $x(x\in [a,b])$，那么 x 一定可以表示为 $x=a+(x-a)，(x-a)\le(b-a)$，那么我们想办法把 x 的下界去掉即可。
如果这一条边 (u,v) 的流量在可行范围之内，那我们可以先将这条边流入流量中为 a 的部分短接到 T，即 (u,T)=a，这条短接的边一定满流。同时将 S 也短接一条为 a 的边到 v，即 (S,v)=a，同样是必须满流的边，此时我们就可以放心设置 (u,v)=b-a 了。这样，我们巧妙地躲过了下界的限制。还有，这里说的 S 和 T 不是原图的 s 和 t，我们还需要将 $(S,s)=+\infty$,$(t,T)=+\infty$连接，组成一幅完整的网。现在就可以顺利求出 F(S,T) 了。

还余下一个问题，如何通过新图的流量计算原图的流量呢？我们讨论一下：

• 几条短接的边没有满流：原图无解。
• 几条短接的边满流，所有边的下界和为 W：则原图的最大流 F(s,t)=F(S,T)-W。

具体原因可以感性地证明 F(S,T)=F(s,t)+W：首先 F(s,t) 的流量包含在了 F(S,T) 中，每个 a 又由于短接而全部被计算了一次。又因为 F(s,t) 和 W 并不冲突，所以 F(S,T)=F(s,t)+W。

b. 有上下界循环可行流

循环流的定义是：每一条边的流量在界定范围内，每个节点的收支平衡。

为了构造循环流，我们可以先将下界限制去除。即：先强行让每条边的流量就是最小流。这样的结果就是满足了边的限制，但没有满足点的限制，下面我们将通过基础网络流使点的限制也满足。

由于节点的收支不平衡，所以有的节点会由于收大于支而出现囤积的流量，另外的则会缺少流量。我们下面的工作将是用每条边剩余的可行流量把存在囤积流量的节点的流量分配到缺少流量的节点，即 “劫富济贫”。

具体怎么做呢？感性地，将边想象成管道。每条管道被拆成了两条并行的管道 $A_i,B_i$，$A$用来运输流量下界，$B$运输下界与上界之间的那部分流量。当我们强制使 $A$满流时，每个节点多余或不足的流量 $S_i$将利用 $B$管道运输。

而上面这个情景与下面这个是等同的：

有一个由 $B$种管道组成的管道网络，每个节点从外界输入或向外界输出 $S_i$的流量，问 $B$管道能否运输外界给予的流量。

这样一想，就很清楚了。建图方法也显而易见了。

• 先让每条边满足下界，求出每个节点的 $S_i=\sum in-\sum out$
• 原图的 $f(u,v)\in [a,b]$对应新图的 $f(u,v)\in [0,b-a]$
• 新图建立边 $f(S,i)=S_i \ (S_i \geq 0)$或 $f(i,T)=|S_i|\ (S_i \leq 0)$

如果新图的 $MaxFlow(S,T)$使的所有步骤 3 建立的边都满流，则原图存在循环可行流，每条边的流量为新图该边的流量+该边下界流量。

c. 有上下界最小流

先明确一个定理：

先计算原图最大流，再添边计算流量变化，与先添边，再一起计算总流量相比，可以保证添的边上流量最小.

这样，我们就可以利用循环流求得最小流。

具体方法是：

先跑 $MaxFlow(S,T)$，再添边 $f(T,S)\in [0,\infty]$，再计算循环可行流。这样保证了新添的边的流量最小，即原图的 $Flow(S,T)$最小。

2. 最小 (大) 费用最大流问题

增广路的求解不在使用 dinic 算法，而是用 SPFA 每次寻找最短 (长) 的一条边。根据网络流的贪心原则，我们最终找到的一定也是最大流。如下是一个最小费用最大流的代码片段。

int q[MX], pre[MX], dis[MX], inq[MX];
int spfa(int &flow, int &cost)
{
    int h=0, t=1, x, y, now, mxf = +oo, cst = 0;
    memset(dis, 0x3f, sizeof(dis));
    memset(inq, 0, sizeof(inq));
    memset(pre, 0, sizeof(pre));
    q[++h] = S;
    dis[S] = 0;
    pre[S]--;
    while(h >= t)
    {
        x = q[(t++)%MX];
        inq[x] = 0;
        for(int i=fst[x]; i!=-1; i=nxt[i])
        {
            y = e[i].v;
            if(e[i].c && dis[y]>dis[x]+e[i].w)
            {
                dis[y] = dis[x]+e[i].w;
                pre[y] = i;                       //记录节点的前驱
                if(!inq[y]) q[(++h)%MX] = y, inq[y] = 1;
            }
        }
    }
    if(dis[T] > +oo) return 0;                    //没有増广路
    now = pre[T];
    while(now != -1)                              //找到增广路上的边权和
    {
        mxf = min(mxf, e[now].c);
        cst += e[now].w;
        now = pre[e[now].u];
    }
    now = pre[T];
    while(now != -1)                              //增广后修改边的流量
    {
        e[now].c -= mxf;
        e[now^1].c += mxf;
        now = pre[e[now].u];
    }
    flow += mxf;
    cost += cst*mxf;
    return 1;
}

int mcf()                                        //minimum_cost_flow
{
    int flow = 0, cost = 0;
    while(spfa(flow, cost));
    return cost;
}

3. 边权变化的费用流

这类费用流的通性是：费用与流量不成线性关系。但是这种函数我们依旧可以用线性函数拟合。
例如：

• 一条边的边权在经过一次后改为 0：这条边拆成两条边，第一条容量为 1，权值不变；第二条容量为 $+\infty$，权值为 0
• 一条边的权值与流量成二次函数关系 (整数流量)：这条边拆成多条边，每条容量为 1，权值分别为 1,3,5,…
• 一条边的权值与流量成二次函数关系 (实数流量)：二次函数关系可以用特殊方法解决，这里不在赘述。

等等等等，我们依旧不需要改变网络流算法，而是在图上做手脚。

4. 循环费用流

比如最大费用循环可行流，可以不停用 SPFA/BELLMAN_FORD 找最大权环，将这个环增加流量。这样可以保证最后找到最大费用的循环流。

5. 动态添边的网络流

对于动态添边，动态求解的网络流，我们可以在原图添边后不重新进行所有的增广操作，而是直接在原残量网络上添边，增广。这样做并不会导致最终答案变化。我们可以这样理解：之前这条边其实一直存在，只是我们没有用它增广罢了。现在添边意味着我们可以通过它增广。这样依旧可以求出当前图的最大流、最值费用流等值。

6. 二分图相关问题：

我们需要分析的是：最大匹配与最小顶点覆盖数、最小边覆盖数、最大点独立集之间的关系。

定义：

• 最大匹配数：二分图中边集数目最大的匹配数
• 最小顶点覆盖：用最少的点，让每条边都至少与其中一个点相连
• 最小边覆盖：用尽量少的边，让每个点都至少与其中一个边相连
• 最大独立集：选尽量多的点，让它们亮亮没有相连的边

a. 最小顶点覆盖=最大匹配数 (König 定理)

设最大匹配数为 n，最小顶点覆盖为 m。
首先我们证明 $m\geq n$：如果从最大匹配看最小顶点覆盖，那么最大匹配中的每一条边都没有公共顶点，故覆盖它们至少需要 n 条边，即 $m\geq n$。
我们再证明 $m\leq n$：如果从最小顶点覆盖看最大匹配，那么一个最小顶点覆盖一定可以转化成一个最大匹配，这个最大匹配的每一条边都至少覆盖一个顶点覆盖中的顶点。所以 $m\leq n$。
那么，我们就推出了：$m=n$，也就是说二分图的最小顶点覆盖=最大匹配数。

当然，这只是比较感性的证明，更严谨的证明可以参考 König 定理。

另外，根据 König 定理，我们可以得到输出最小顶点覆盖的方案的算法 (如在 UVa11419 中的应用)。

b. 最小边覆盖=顶点数-最大匹配数

设最大匹配数为 n，最小边覆盖为 k，图为联通图。
使用一点贪心的策略：由于一条边只能至多覆盖 2 个顶点，所以我们需要用尽量多的边覆盖两个顶点，尽量少的边覆盖剩下的点。这样得到的边覆盖一定是最小的。
由于最大匹配中的边可以覆盖两个点，且不存在别的方案比最大匹配中的边多，所以我们先用这些边覆盖两个点。余下的顶点每个顶点用一条边覆盖。如果剩下的点有 a 个，那么 2n+a=|V|，所以我们总共使用的边数 (n+a)=|V|-n。

c. 最大独立集=顶点数-最大匹配数

设最大匹配数为 n，最大独立集为 d。
根据定理 1：n=m 我们可以知道，最大匹配的边对应的 2n 个顶点中有 n 个顶点最为最小顶点覆盖，那么剩下的|V|-n 个点一定会两两独立，否则其中至少有一个顶点会出现在最小顶点覆盖中，与题设不符。因此这|V|-n 个顶点就是最大独立集。

7. 子图相关问题

a. 最大权独立子图

最大权独立子图指的是求有向图的一个点权和最大的子图 P(可以就是原图)，使原图中不存在任何一条边 $(u,v),(u\in P,v\not\in P)$。
也就是说 “肥水不流外人田”，我们需要找到一个只能进来不能出去的子图。

怎么做呢？我们可以先把权值按正负分类，正权点在左，编号 Xi，负权点在右，编号 Yi。
如果我们选则了一个正权点 X，为子图增加了 Xi 的贡献，那么 X 指向的负权点 Y 会为子图扣除|Yi|的贡献。为了利益最大化，如果我们选择的 X 的贡献可以弥补 Y 的损失，那么我们选择 X，否则我们不选 X。即：贡献随讨论的 X 的增多一定是单调不降的。换成数学语言，对于一组 {Xi},{Yi}，对原图的贡献一定是 $|X|-min(|X|,|Y|)$。(表述有些含糊，但是我们需要意会)。这样一来，我们就可以利用最小割来解决了。

我们建立一个新图，图中左边的点对应原图每个正权点，右边的对应原图每个负权点。如果原图存在点 Xi，那么原图左边也有 Xi，同时建立边 (S,Xi)=|Xi|，如果原图存在点 Yi，那么原图右边也存在点 Yi，同时建立边 (Yi,T)=|Yi|。原图所有边也都加入到新图中，权值为正无穷。这样，新图最大流 (即最小割) 即是求出了 min(|X|,|Y|) 的值。我们拿所有正权点的权值和减去 F(S,T) 即是最大权独立子图的权值和。

与最小顶点覆盖问题一样，这个问题的数值答案和方案答案也是有一定距离的，下面要说明如何通过最大流求得具体的最大权独立子图。

对于一个求出了最小割的图，其 S 点可以通过正向边和反向边到达的点为原图中被选择的点。原因：无法访问的点为被割掉的边截断的点，故我们不需要选择。反之没有被截断的点就是我们要选择的点。而且可以知道这些点权值和的确为 $(\sum |Xi|)-F(S,T)$。

b. 最大密度子图

最大密度子图类似于最大权独立子图，是一个点集 P 和边集 Q 构成的子图，其中 $Q={(u,v)|u\in P,v\in P}$，而且 $\frac{|Q|}{|P|}$最大。
简单的理解就是边数/点数最大的图。每一条边都连接这这个图中的两个点。

此题的高效求解需要结合最大权闭合子图和分数规划的思想，故也出现在了这篇文章里。

设原图中密度 ($|E|/|V|$) 大于等于 x 的子图的数量为 num(x)，那么 num 函数一定随 x 递增而递减。所以我们可以用二分法求这个函数值恰好不为 0 的 x 值。

如果我们需要判定是否存在密度为 x 的子图，我们可以用以下的方法：

由于每选择了一条边，与它相连的点必须被选择。那么如果我们设边权为 1, 点权为-x，若我们按照这种策略找到了权值和大于 0 的子图，则证明存在密度为 x 的子图，反之不存在。

所以我们可以建立二分图，通过求解最大权闭合子图获得答案。建立一个二分图，左边的顶点 Xi 对应原图的边，连边 (S,Xi)=1，右边的顶点 Yi 对应原图的点，连边 (Yi,T)=x。按照最大权闭合子图的算法，如果你得知最大权为 0 时 (即最大权的子图就是屁都不选)，你就要含泪调小二分上界继续查找更小的 x，反之你可以自信地调大下界，尝试更大的 x。这样，我们通过对 x 的二分+判定，找到了满足要求的 x，使 num(x) 恰好不为 0。由于这时的 x 可能为小数，所以我们需要对实数进行二分，在实数意义下跑网络流，此时需注意 eps 等的设定。

其他

a. Dilworth 定理

图的最长反链长度等于最小链覆盖。

该定理是针对什么鬼偏序集上的。其具体内容是：反链是一种偏序集，其任意两个元素不可比；而链则是一种任意两个元素可比的偏序集。Dilworth 定理说明，存在一个反链 A 与一个将序列划分为链族 P 的划分，使得划分中链的数量等于集合 A 的基数。

链，我们可以具象地理解为图上的一条有向边连成的路，因此反链就是图上的一组点，两两不可达。

证明：略

b. 霍尔定理

二分图的完美匹配存在的充要条件是：二分图左部任意 k 个元素在右部共有 k 个以上的相邻元素。

证明：略