Nikkukun's Blog
0%

网络流总结

发表于 更新于 分类于 阅读次数： 37

网络流，就是一张有向图中给每一边分配一个容量，流可以沿着有容量的边移动。对一个给定的网络，其一个可行流为从源点到汇点的一种流量方案。

网络流问题就是解决最大流、可行流、费用流等抽象问题的一种模型。对一个可行流来说，它有如下特性：

  • 除了源汇点外，每一个点的入流与出流相等
  • 经过每条边的流量不超过该边容量上限

则最大流就是到达汇点的流量最多的一个可行流，它也满足上述性质。

## 最大流

求最大流可以采用 Dinic、SAP、ISAP 等算法，但我们主要介绍 Dinic。Dinic 算法分为寻找分层图与增广两个部分。下面不加解释地放上 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
struct Dinic{
    struct Edge{int v,res;};
    vector<Edge> edg;
    vector<int> a[V];
    int st,ed;

    void AddEdge(int u,int v,int cap){
        edg.push_back((Edge){v,cap});
        edg.push_back((Edge){u,0});
        int siz=edg.size();
        a[u].push_back(siz-2);
        a[v].push_back(siz-1);
    }

    int dep[V];
    bool BFS(){
        memset(dep,-1,sizeof(dep));
        queue<int> q;
        q.push(st);dep[st]=0;

        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<a[u].size();i++){
                Edge e=edg[a[u][i]];
                if(dep[e.v]==-1&&e.res>0)
                    q.push(e.v),dep[e.v]=dep[u]+1;
            }
        }

        return dep[ed]!=-1;
    }

    int cur[V];
    int DFS(int u,int minF){
        if(u==ed||minF==0)return minF;

        int tmpF,sumF=0;
        for(int &i=cur[u];i<a[u].size();i++){
            Edge &e=edg[a[u][i]];
            if(dep[e.v]==dep[u]+1&&(tmpF=DFS(e.v,min(minF,e.res)))>0){
                e.res-=tmpF,edg[a[u][i]^1].res+=tmpF;
                sumF+=tmpF;minF-=tmpF;
            }
            if(minF==0)break;
        }

        return sumF;
    }

    int MaxFlow(){
        int ret=0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            ret+=DFS(st,INF);
        }
        return ret;
    }
};

上述代码用残量表示边的流量数据。对这份代码的解释很容易在网络上找到，在此不做赘述，而只点出实际写时的易错点：

  • 寻找分层图时，不能经过残量为 0 的边。
  • 利用当前弧结构保存时，每一次寻找增广路前要清零。并且寻找增广路时要使用引用来更新当前弧。
  • 寻找增广路时要对当前边进行修改，因此要对边使用引用而不能单纯复制内容
  • 对边的四个操作要保证修改的对象和数值是否正确
  • 如果流量为 double 类型，需要 DCmp 判断是否为 0，而不能直接与 0 比较

这是一些很 naive 且很容易忘记的错误。放出以警示自己。

### 带上下界的流

带上界的流一般都采用拆点的方式建图来保证其上下界功能。考虑好必须经过的流量是哪些，可以经过的流量是哪些。

#### 带上下界可行流

##### 无源汇

对于 $E = (u , v) ，若其流量限定为 [low , upp]$，则我们可以先考虑特殊情况。

  • 没有下界：普通的网络流，从 u 向 v 连容量为 upp 的边。
  • 没有上界：u 节点必须输出 low 流量，v 节点必须流入 low 流量。根据这个条件，可以考虑从 u 向 t 连流量为 low 的边，从 s 向 v 连流量为 low 的边，这样就满足了上述条件。

我们发现这两个不互相干扰，一起使用即可。明显，整个网络拥有一个可行流的等价条件是，新增的下界边都满流，否则没有可行流。

由于新网络入流与出流相等，而无源汇的网络满足流量平衡，因此 s 的出流等于 t 的入流，也就满足了新增加的边如果从 s 得到了流量，则一定跑到了 t，而不会中途消失。此时 t 的最大流就是经过这些下界边的总流量。

##### 有源汇

从 t 向 s 连一条容量为 ∞ 的边，这样网络就变成无源汇的上下界，跑可行流即可。之所以需要变成无源汇而不能拆边后直接跑，是因为无源汇的网络做法考虑了流量平衡，而有源汇的网络明显源汇是不平衡的。如果不连 $(t , s) 的边，那么改建后原网络的s$ 根本就没有流量。这很明显不可行。

#### 有源汇带上下界最大流

##### 普通做法

我们的立足点是无源汇上下界可行流的求法，因此考虑把有源汇先转成无源汇。按照无源汇可行流的方法建图并跑最大流，得到的是一个原图的可行流，此时的下界应该是填满的（显然，不填满就连可行流都没有）。在残余网络上从原图的 S 到 T 跑最大流就是答案。（当然我不是很理解。）

##### 二分做法

我们仍转换为无源汇，但是设从 T 到 S 的边有下界 x，并跑无源汇可行流。明显，如果新图具有可行流，则说明原图能有 x 的流量从 S 到达 T，否则没有。这个性质可以二分。

#### 带上下界最小流

如果不带上下界，则最小流就是零流，没有什么好求的。

##### 普通做法

考虑转化为无源汇，但这次我们不连接从 T 到 S 的边，直接跑 SuperS 到 SuperT 的最大流。再加上从 S 到 T 的边，从 SuperS 到 SuperT 跑一次最大流。若从 S′ 出发的边满流，则 (T,S) 的流量为最小流，反之无解。（当然我不是很理解。）

##### 二分做法

我们仍转换为无源汇，但是设从 T 到 S 的边有下界 x，并跑无源汇可行流。明显，如果新图具有可行流，则说明原图能有 x 的流量从 S 到达 T，否则没有。这个性质可以二分。

#### 总结

我们所有上下界流的基础都是建立在上下界无源汇可行流上，因此这个模型的转换是很重要的。另外，上下界最大 / 最小流的二分解法虽然比普通解法多出一个 log，但是却很容易理解。实际运用上应该是足够的。

## 最小割

流网络 $ G = (V , E) 的割（Cut） [ S , T ] 将点集 V 划分为 S 和 T ( T = V − S )两个部分，使得源 s ∈ S 且汇t ∈ T 。符号 [ S , T ] 代表一个边集合 { u , v | u , v ∈ E , u ∈ S , v ∈ T } 。割 [ S , T ] 的容量（Capacity）定义为 c ( S , T ) ，一般记为 c [S , T] $。一个网络的最小割也就是该网络中容量最小的割。（定义来自《最小割模型在信息学竞赛中的应用》 胡伯涛）

注意边集中方向为 T→S 的边的容量不计算在割集内。即最小割的容量只为顺着 S→T 到达的边的容量和。

最小割拥有一些不错的性质：

  • 最小割将点集分割成两个部分，且最小割只包含了两端点属于不同点集的边的容量
  • 最大流最小割定理：一个网络中的最大流等于最小割

第二个性质很重要，它给了我们一个求最小割的方法。而第一个性质给了我们一个转换模型的思路。我们给出如下性质：

  • 最小割一定是最大流中的满流边，但满流边不一定是最小割中的边

这个性质的反例可以在论文中找到。因此寻找最小割边时，需要从源点 DFS 顺着有残量的边遍历，则两端点只被遍历一个的边为最小割边。注意这个有残量的边包括网络中的反边，有些点可能能从反边被到达，因此需要 DFS 而不能单独认为满流边就是最小割边。

### 平面图最小割

可以参考论文《两极相通 —— 浅析最大 — 最小定理在信息学竞赛中的应用》周冬。

平面图的对偶图：把平面图的面当点，连接两个面的边当两个点的边的图。平面图有不错的性质：

  • 欧拉公式：顶点数 $ + 面数 - 边数 = 2$
  • 平面图的对偶图也是一个平面图

对一个源汇点都在无界面的边界的网络，如何根据平面图求它的最小割？我们从 S 到 T 连接新边创建出附加面，并对这个图创建对偶图，其中 S′ 和 T′ 为对偶图在附加面与无界面的点。则我们画个图就能发现，$S' 到 T'$ 的一条路径就是原图的一个割。因此原图的最小割相当于新图的最短路径。

我们得到一个感受：当原问题不好入手时，考虑它的对偶问题。

### 最大权闭合图

这类题目是求具有依赖关系的最大权子图：选择 A 会有一定权值，但同时要选择 B 和 C，它们也会产生权值，这样的关系构成一张有向图。选择有向图的一个子图，使得若 v 在点集，则 v 的出边指向的点也在点集。

对这类题目的详解在论文有。此处只阐明算法：

  1. 对原图的所有边容量赋为 ∞
  2. 从 S 向正权点连权值为 w 的边
  3. 从负权点向 T 链权值为 −w 的边
  4. 最大权闭合子图 = 正权点权和 - 新图最小割

## 二分图最大匹配

二分图本身就有一个两端属于不同点集的边集，因此二分图常常被询问最大匹配。最大匹配即，选定一个边集，使得边集中的所有点不相交。二分图的最大匹配有 O(nm) 的匈牙利算法（Hungarian Algorithm），非二分图的最大匹配需要带花树算法（Blossom Algorithm）。

不加注释地给出匈牙利算法代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool vst[N];int lnk[N];
bool DFS(int u){
    for(int v=1;v<=nV;v++)
        if(g[u][v]&&!vst[v]){
            vst[v]=1;
            if(!lnk[v]||DFS(lnk[v])){
                lnk[v]=u;
                return 1;
            }
        }

    return 0;
}

int ans=0;
for(int i=1;i<=nV;i++){
    memset(vst,0,sizeof(vst));
    if(DFS(i))ans++;
}

这个算法给出的是邻接矩阵做法，我们可以很轻易地改为邻接表。需要注意的点：

  • 每次开始搜索前，清空访问数组
  • 只有没有访问的节点可以操作

## 图的性质

明确以下概念：

  • 点相关
    • 最小点覆盖
    • 最大独立集
    • 最小点权覆盖
    • 最大点权独立集
  • 边相关
    • 最小边覆盖
    • 最大匹配

这些概念都可以在论文中找到具体定义，但我们重点讨论它们的性质：

  • 最大匹配数 + 最小边覆盖数 = 顶点数（条件：联通图）
  • 最大独立集 + 最小点覆盖数 = 顶点数
  • König 定理：最大匹配数 = 最小点覆盖（条件：二分图）
  • 最大流 = 最小割
  • 最小割 = 最小点权覆盖集（条件：二分图）
  • 最小点权覆盖集数 + 最大点权独立集数 = 顶点数（条件：二分图）

大部分性质都可以概括为：最值 $ = 最值，最小 + 最大 = ​$ 顶点数。后三条可以得到一个计算最大点权独立集的有效算法。具体的讨论和证明可以参考《两极相通 —— 浅析最大 — 最小定理在信息学竞赛中的应用》周冬。

## 最小费用最大流

给网络中的每一个边一条边权，求使得最大流的情况下的最小费用。下面不加注释地给出代码：

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
47
48
49
50
51
52
53
54
55
56
57
struct Dinic{
    struct Edge{int v,w,res;};
    vector<Edge> edg;
    vector<int> a[V];
    int st,ed;

void AddEdge(int u,int v,int w,int cap){
    edg.push_back((Edge){v,w,cap});
    edg.push_back((Edge){u,-w,0});
    int siz=edg.size();
    a[u].push_back(siz-2);
    a[v].push_back(siz-1);
}

int dis[V],pa[V],det[V];
bool SPFA(){
    static int inQ[V];
    memset(inQ,0,sizeof(inQ));
    memset(dis,0x3f,sizeof(dis));
    deque<int> q;q.push_back(st);
    dis[st]=0,inQ[st]=1,det[st]=INF,pa[st]=-1;

    while(!q.empty()){
        int u=q.front();q.pop_front();inQ[u]=0;
        for(int i=0;i<a[u].size();i++){
            Edge &e=edg[a[u][i]];
            if(e.res>0&&dis[e.v]>dis[u]+e.w){
                dis[e.v]=dis[u]+e.w;
                det[e.v]=min(det[u],e.res);
                pa[e.v]=a[u][i];
                if(!inQ[e.v]){
                    if(!q.empty()&&dis[q.front()]>=dis[e.v])q.push_front(e.v);
                    else q.push_back(e.v);
                    inQ[e.v]=1;
                }
            }
        }
    }

    return dis[ed]!=INF;
}

void Augment(int &w){
    w+=dis[ed]*det[ed];
    int u=ed;
    while(u!=st){
        edg[pa[u]].res-=det[ed];
        edg[pa[u]^1].res+=det[ed];
        u=edg[pa[u]^1].v;
    }
}

int MaxFlowMinCost(){
    int ret=0;
    while(SPFA())Augment(ret);
    return ret;
}

要点：

  • 增广过程与 SPFA 相似，但仍要注意只有有残量的边可以通过。
  • SPFA 过程注意是否出队入队，是否取消标记，是否入对位置正确。

### 费用流拆边

一条边所花费的费用是随流量线性增长。如果呈二次增长，甚至三次增长呢？需要拆边。

假设 $f 为流量，cap 为边容量，w = f ^ 2 为费用，则当 f = 1 时 w = 1 ， f = 2 时 w = 4， f = 3 时 w = 9 。我们把边拆为 cap $ 条，每条容量是 1，费用分别是 1,3,5,… 则不难发现在流量相同时，费用会选择最小的 $ f 条，而这 f 条的费用加起来刚好为 w= f ^ 2$。当流量呈更复杂的多项式时，可以利用导数将边拆分。但很明显拆边有前提：流量必须是整数，多项式导数必须递增。

### 带权二分图匹配

如果有权，则可以给边赋权用费用流求解匹配。从 S 向 X 集合、从 Y 集合向 T 连权值为点权、容量为 1 的边，跑最大流最小费用即可。

## 练习

### 最大流

####USACO4.2.1 草地排水

最大流模板题目。

####BSOJ1721 上下界可行流 & BSOJ1723 上下界最大流 & BSOJ1725 上下界最小流

上下界网络流的练习题。

####BSOJ2547 网络流 24 题 - 6 最长递增子序列

第二问可以考虑每个点只能被选一次，并且假设当前节点结尾的 LIS 为 $ d ，则当前节点只能向后面LIS为 d + 1 $ 的节点（否则不是 LIS）连容量为 1 的边。最后 $ S 连 d $ 为 1 的点，$ d 为全局LIS的点向T连，跑最大流即可。第三问只需要修改部分点流量为$。

####SDOI2015 星际战争

二分答案判断最大流是否足够。注意精度。

### 二分图最大匹配

####SCOI2015 小凸玩矩阵

二分答案 ans，X 集合为行，Y 集合为列，选中一个元素等于匹配两个点，每次只能选择小于等于 ans 的元素。判断这些元素（匹配）是否有 $ (n - k + 1) 个。注意第k大而不是第k$ 小。

####USACO2005NovGold Asteroids

有行星的位置连接一条边，求最小点覆盖。可转化为最大匹配。

####USACO2005JanGold 泥泞的牧场

注意到每个点只能被横行或纵列覆盖（可以同时覆盖）。对于连续的泥泞，我们一块木板盖上是最好的。因此我们可以把图分块。横向的分块与纵向的分块编号后，一个泥泞就只能对应一条横向与一条纵向分块的交点了。

题目相当于转化为选择尽量少的分块，使得每个交点都被覆盖。如果把分块变成左右两端的点，交点变为它们之间的边，则原题目化为最小点覆盖。为什么可以转化？我们发现两个块要么有交点，要么没交点，并且只有横向块与纵向块相交，这完全符合二分图性质。

####BSOJ1775 xinyue 的约会

同上，但需要考虑有些边不需要添加。

####BSOJ2569 网络流 24 题 - 3 最小路径覆盖

把每个点拆成入点和出点，这样一个匹配就是一个边。在匹配中，每一个点的前驱和后继是唯一的，而只有起点不存在前驱，终点不存在后继。有多少个点没有前驱或后继，就有多少条路径。因此对于一个匹配，其路径数 = 点数 - 匹配数。

因此，最少路径 = 点数 - 最大匹配。

有关路径的问题可以将其拆成二分图，再观察路径的性质。

### 最小割

最小割的题目算是比较有价值，也是比较难转换的模型题目。

####POJ2125 Destroying the Graph

每条边可以被入点破坏也可以被出点破坏。因此构造二分图求最小割。

####POJ3469 Dual Core CPU

考虑没有额外代价的情况，则一个任务只能在两个 CPU 的其中一台运行。这个就是最小割模型，$S 向任务 i 连边权为 a_i的边，i 向 T 连边权为 b_i的边，则最小割就把所有点集分成两个部分（要么属于 S ，要么属于 T $），且使得所有割边代价最小。

考虑加上代价。我们希望当 $ a 与 b 不在同一个点集时能有额外的权 w _i，这很像最小割的定义，因此我们考虑把w_i也加入到最小割。具体做法是在 a 与 b 之间连边权为 w_i的无向边，这样当 a 与 b $ 在同一个集合时此边不会是割边，而不在同一个集合时，会把额外代价计算。这就解决了问题。

往往要从定义出发：割边是连接两个属于不同集合的点的边集。下面的题目也显示出这个特点。

####SPOJ839 Optimal Marks

我们发现因为存在位运算，所有边权的总和最小等价于边权的每一位总和最小。因此单独考虑每一位，且每一位都只有 0 和 1 可以取。注意到 xor 的定义是两个数不同则为 1，相同为 0，边权只有端点的两个数不同时才被计算，这和最小割的定义同样很像。

因此最小割模型显然。把两个集合当成选择的值，向每个点连接容量为 ∞ 的边，有边相连的两个点连容量为 $ 1 的边。这么做的目的是：割边只能在∗∗特定的边∗∗取到，而不能在∗∗容量为∗∗$ 的边取到。对每一位跑一次最小割即可。

我们得到一个直观的感受：如果一条边不想成为割边，只需要把容量设为 ∞ 。

####ZJU2676 Network Wars

见论文。此处重点讨论细节。

对给定网络，我们需要选出一个最小割集。由于分数规划使得边权可能为负，而负边权相当于反边，是不会被计算在最小割的容量的，因此需要手动叠加，而只对边权 >0 的边求割。

####BSOJ2550 网络流 24 题 - 9 方格取数问题

对棋盘黑白染色后发现相邻的不同颜色点之间只能选择其中一个。因此把有冲突的点连边，求最大独立集（权为 1 的最大点权独立集）即可。注意是二分图，转化求最小点权覆盖集 → 最小割 → 最大流。

####CQOI2017 老 C 的方块

题目描述很复杂，大致就是在一个特殊的网格上不能有特定图形出现，而去除一个网格需要一定费用。

然后我们观察四个图，发现特殊边两侧刚好连接两个格子。“某些状态不能共存，而去掉某个状态需要一定代价” 的想法让我们想到最小割（虽然数据范围上不是这样的）。因此有这些形状的格子要连接起来，并且至少有一个连接源点或汇点。经过一番构图，我们构造出下面这种网络：

⋮⋮⋮⋮⋮⋮↓⇐←←ST←←⇐←⋯↓↑↓↑↓↑TS→→⇒→→TS⋯↑↓↑↓↑↓↑⇐←←ST←←⇐←⋯↓↑↓↑↓↑TS→→⇒→→TS⋯↑↓↑↓↑↓↑⇐←←ST←←⇐←⋯（有没有想到洋流图）

每个交点是原图中的一个方块，双线箭头代表图中的特殊边。我们在这张网络图上能发现原图中的四种方块都对应一条从 S 到 T 的边，我们只需要求最小割就是最小花费。问题是怎么设置边权。

明显处于 S 和 T 上的点应该各自连 w 到 S 或 T，那特殊边两侧的两个方块呢？如果要删掉一个方块，则只需要删掉一个就好了，两个同时删是不划算的。因此我们只需要给特殊边设两个方块的较小 w 即可。

虽然本题点的规模达到了 105，但棋盘很大，连边只在相邻的方块出现，因此边数不大。跑跑最大流就过了。

是道建图好题。我们可以得到一个直观感受：最小割可以解决不共存的最小代价问题。这跟上面利用割的定义最小化分点代价不同，其出发点是源汇点的联通性。

### 最大权闭合图

####BSOJ2543 网络流 24 题 - 2 太空飞行计划

很明显的最大权闭合图模型，直接转化。

####NOI2006 最大获利

见论文。选定一个边同时要选定两个点，转化模型。

####TJOI2015 线性代数

转化题目后发现相当于有许多物品，要得到物品 $ i 和 j 需要先选定 i 和 j，而选定 i 和 j$ 都需要代价。接着就可以做了。

有个神奇的做法是暴力寻找不要什么物品，时间复杂度 (n3n)，跑起来还挺快。

### 费用流

####BSOJ4914 疯狂的方格取数

拆点。由于网络流与边有关，因此和点有关的题目往往需要把点拆掉来建立边。

####ZJOI2010 网络扩容

第一个最大流很简单。

第二个我一开始估计是在残余网络上操作，然后跑个 DP 计算每条路径扩展 k 所需要的费用，再统计和即可。不过这不好实现还容易 TLE。发现所需费用是费用流的表达式，但是如果直接跑费用流，我们希望有容量的边不计算权值，没流量的边计算权值，怎么办？

残余网络中，原图都加一条边权为 w，容量为 ∞ 的边。再从超级源点 s 向 1 建边权为 0，容量为 det 的边。这样，在跑费用流的时候，如果一个边有流量就会优先选择这条没有花费的边，否则只能选择有花费的新边。

这个思路挺巧妙的，虽然我觉得对 n=1000,m=5000 的数据跑 O(n2m) 有点夸张。不过据说 Dinic 的复杂度和 SPFA 一样是个迷，因此还是可以跑的。

####SCOI2007 修车

本质上是一个打水问题，不过在不同的维修队列里花费时间也不一样。

费用流模型不难想到，可是具有后效性。然而我们发现把每个维修人员的

【未完成】

####NOI2008 志愿者招募

题目太神，不会做。但是还是放上 BYV 的题解。

具体的思路是把不等式添加变量修改为等式，这样容易思考。其次发现每个人都从某段时间开始，某段时间结束，可以考虑到差分。两者结合就得到了新的等式，并且由于差分的特性，每个有关变量都刚好出现两次且符号相反。

啧啧称奇。（虽然我不知道为什么推出来之后，需要求最大流。）

## 总结

网络流通常用来求一类有限制（选择次数、不可同选）的题目。建模相比起算法往往更重要，因此如何构造网络是网络流题目的一个重点。

  • 需要掌握图的点与边集关系，尤其是二分图
    • 最大匹配数 + 最小边覆盖数 = 顶点数（条件：联通图）
    • 最大独立集 + 最小点覆盖数 = 顶点数
    • König 定理：最大匹配数 = 最小点覆盖（条件：二分图）
    • 最大流 = 最小割
    • 最小割 = 最小点权覆盖集（条件：二分图）
    • 最小点权覆盖集数 + 最大点权独立集数 = 顶点数（条件：二分图）
  • 网络流的建模入手点
    • 有关选择的依赖关系的问题，可以考虑最大权闭合图
    • 有关路径的问题可以按照出边入边将其拆成二分图，再观察路径的性质
    • 有关等式或不等式，考虑流量平衡（如上下界网络流、志愿者招募）
    • 有关不共存的最小代价，考虑最小割使源汇不联通的性质，在不共存状态间连边，再与源汇连边求最小割