基本概念

已知有向图 映射 称为 中每条边的容量, 是一个非负实数, 记作 或者 在 中有两个特殊顶点 分别称作源点和汇点, 这样可以用一个五元组 表示一个容量网络 . 定义每条边 的可行流为 映射 表示大小为有 的流量流经边 需满足两个要求:

1: 每条边的流量不能超过该边的容量, 即

2: 对于所有的非源点和汇点的点, 流入每个点的流量之和等于流出每个点的流量之和, 即 有

这很像基尔霍夫电流定律, 即流入每个结点的电流等于流出每个结点的电流. 为了方便, 用 分别表示流入 和流出 的流量, 在定义了广义结点后, 的含义同样适用.

在上面两个要求的定义之下, 可以定义整张网络的流量 为原点 的净流出量, 或者汇点 的净流入量, 即 最关注的问题是最大流问题, 也就是求出一张容量网络的最大流量.

如果对于结点 同时有 , 可以定义广义节点 或者在 之间插入一个节点 并使 或者 在后面就默认两个结点之间有且仅有一条边.

容量网络中另一个有用的概念是割集: 对于 若 满足 则称 为 的一个割集, 记作 (这只是一种形式上的记法). 割集是一些边的集合, 这些边的流量之和 称为割集的容量, 记作 割集就是把 分成两部分后, 端点分别在两部分的那部分边的集合, 和二分图很是相似.

若将 均看作广义节点, 那么整张网络中只剩下这两个结点, 此时显然有 以及

最关注的问题是最小割问题, 也就是求出一张容量网络的所有割集中容量最小的那个.

下面通过线性规划理论论述最大流与最小割的关系.

最大流与最小割都可以写成线性规划问题的形式.

最大流:

最小割:

最大流问题和最小割问题实际上互为对偶问题, 下面证明这一结论.

考虑用式 则最大流问题是如下的线性规划问题 一共 个约束条件( 个容量限制, 个平衡条件) , 个变量 , 则对偶问题有 个变量, 个约束条件, 且变量可以写为 与 个不等式约束条件进行对应; 与 个等式约束条件进行对应, 于是对偶问题为 其中 是自由变量. 由于 因此每个 都取最小值时 取得最小值, 此时 因此上述优化问题就可以改写为 也就是最小割问题. 这就证得了最大流与最小割问题互为对偶问题.

下面介绍常见的算法.

FF算法

首先是Ford-Fulkerson算法. 最简单的想法是, 从源点开始搜索到汇点的可行路径, 该条路径上的最小容量为该条路径上的可行流, 不断重复该过程, 直到没有可行路径为止, 所有可行流的流量.

给出一些定义:

• 增广路: 考虑从 到 的一条路径, 在该条路径中, 如果所有前向边非饱和, 所有后向边非零流, 则称这样的一条路径为增广路.

FF算法就是通过DFS不断搜索增广路的过程, 需要注意的是, 每找到一条增广路且有 的流流过边 时, 需要再使 的流流过 , 即建立反向边 , 并使得 的流流过 , 这个过程实际上相当于一个撤销返反悔的过程, 即在刚开始搜索得到的可行流可能并不是最优的, 它们中有的边可能并不需要经过.

下面给出FF算法的证明, 即下面的定理:

可行流 是最大流的充要条件是 中不存在增广路.

PROOF 必要性: 如果 是最大流, 且仍然存在增广路, 设增广路可流的剩余流量为 , 显然可以继续从增广路增加流量, 增加 后的流 显然是最大流, 且此时不存在增广路, 这就证得了必要性.

充分性. 假设 中不存在关于可行流 的 增广路, 置集合 , 同时令 , 显然由条件可得 . 对任意 , 必定有 , 即割集中的每条边都是饱和的, 否则, 假设存在 使得 , 由于 , 则 增广路可以延伸到 , 这就意味着 , 这与 显然矛盾, 于是割集 的每条边都是饱和的. 同理可以证明所有的 都是零流的, 即若存在非零流的 , 仍然可以得到 , 矛盾! 于是 这实际上就是最大流.这同时也再一次证明了最大流等于最小割.

FF的时间复杂度: 记 , 且容量均为整数, 则每次搜索后至少会当前可行流的流量至少增加 , 且每次至多遍历所有的边, 于是时间复杂度为 , 与流量的大小成正比.

FF算法的过程, 在基础的DFS基础上, 遍历的时候要给点做一些标记, 包括点是否被访问过的标记, 到当前点 的前一个顶点 和 为前向边还是反向边, 以及到当前点时 的路径上的所有正向边的残存容量与反向边的容量的最小值.

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

// https://www.luogu.com.cn/problem/P3376
#include<bits/stdc++.h>
using namespace std;
int a[205][205]; //采用邻接矩阵
int const inf=0x7777777;
int n,m,s,t,ans=0,isv[105];
int flag=0;
int dfs(int v,int flow){ //_min为这条增广路上的最小容量
    if(v==t){
        return flow; //该增广路的流量
    }
    for(int i=1;i<=n;i++){
        if(a[v][i]>0&&isv[i]==0){
            isv[i]=1;
            int c=dfs(i,min(flow,a[v][i]));
            if(c!=-1){
                a[v][i]-=c;
                a[i][v]=c;//建反边
                return c;
            }
        }
    }
    return -1;
}

void FF(){
    int c;
    while((c=dfs(s,inf))&&c!=-1){
        ans+=c;
        memset(isv,0,sizeof(isv));
    }
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        cin>>a[x][y]; //容量
    }
    FF();
    cout<<ans;
    return 0;
}

EK算法

EK算法并没有在FF算法上做什么改进, 只是换了搜索方式, 即使用BFS而不是DFS. 但是这会使得EK算法的性能好于FF算法, 因为BFS能保证每次找到的增广路是最短的(假设边权为 ), 而DFS为了找到容量最大的增广路可能会绕远路.

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[205][205]; //采用邻接矩阵
ll const inf=0xffffffffff;
int n,m,s,t;
ll ans=0;
queue<int>q;
ll flow[205];//流向每个结点的流量，其中流向源点的流量可以认为是inf
ll last[205];//每个结点的前置结点，默认为-1，即如果为-1表示
int bfs(){
    memset(last,-1,sizeof(last));
    while(!q.empty())q.pop();
    flow[s]=inf;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(u==t){
            break;
        }
        for(int i=1;i<=n;i++){
            if(a[u][i]>0&&last[i]==-1&&i!=s){
                last[i]=u;
                flow[i]=min(flow[u],a[u][i]);//流向结点i的流量是流向u的流量与边(u,i)的当前容量的较小值
                q.push(i);
            }
        }
    }
    return last[t];
}
void EK(){ //要不停地进行bfs，直到无法搜索到汇点t
    while(bfs()!=-1){///每次搜索过后都要更新整张网络
        ans+=flow[t];
        for(int i=t;i!=s&&i!=-1;i=last[i]){
            // cout<<i<<' ';
            flow[last[i]]=flow[i];
            a[last[i]][i]-=flow[i];
            a[i][last[i]]+=flow[i];
        }
    }
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        int x,y;
        ll w;
        cin>>x>>y>>w;
        a[x][y]+=w; //容量
    }
    EK();
    cout<<ans;
    return 0;
}

Dinic算法

FF算法每次只能找到一条增广路, 同时每次寻找的时候都需要重新进行标号, 然后在寻找新的增广路时, 原来顶点的标号可能不变, 这样就造成了重复标号, Dinic算法就是这样的思想, 借助已经做过的标记, 防止做重复性工作来提高效率.

现在定义关于容量网络 上的可行流 的辅助网络 : , 其中 , 即 并表示不饱和的正向边, 表示流量大于零的反向边. 满足 称为辅助容量, 显然, 也是一个容量网络, 是它的容量, 不难发现, 中的 有向路径均为 中的 增广路.

首先想关注的问题是,辅助容量网络 的最大流和原容量网络 的最大流有什么关系呢? 这是下面的定理:

设 的最大流为 , 则 是它的一可行流, 则 的最大流为 .

PROOF 设 的一个割集为 , 显然它也是 的一个割集, 记作 , 包括 的非饱和正向边和非零流反向边, 设这两者的集合分别为 , 那么可以得到 且 , 这就证得了 , 同时 也为 的最大流.

设 为 上的可行流, 为 上的可行流, 定义 满足对任意 都有 , 那么 也是 上的可行流, 且满足 .

现在在 Dinic 算法中引入分层的思想. 设 的层数为 , 顶点 的层数 定义为 到 的最短路径, 且边权定义为 , 这通过一次BFS便可预处理出, 并令 , 显然要获得最短的可行流, 可行流不可能从高层流向低层, 同时不会经过 的点 . 现在定义分层辅助网络 为删去 中冗余的边和点, 冗余的边和点定义如上, 即高层到低层的边以及层数大于 的点, 用符号表示为 , 且 , . 即 表示第 层顶点的集合, 表示起点为第 层顶点终点为第 层顶点的有向边. 于是 实际上是一个有向无环图, 且只有一个源点和汇点.

如果 中不存在关于 的且不含反向边的增广路, 那么称 为 中的极大流. 显然可行流是最大流的必要条件是可行流为极大流. Dinic算法的关键步骤是求 的极大流, 即在 中找到尽可能多的可行流.

对于每个顶点而言, 能流经该顶点 的最大流量显然为终点为该顶点的边的容量和与起点为该顶点边的容量和这两者之间的最小值, 记作 , 规定 .

求 的极大流的过程也类似于寻找增广路, 但是不像FF算法那样一条一条的找, 而是一次找多条. 在定义过顶点最大流量 后, 只需要删去满足 的顶点及其边, 在剩下的顶点中, 假设 , 那么就把流量 推送到 , 再反向推送到 , 接着删去 及其相邻的边, 然后再删去 中已经饱和的边, 得到新的 , 直到 不存在从 到 的路径为止, 此时便得到了 的极大流 , 接着置 即可, 直到 中也不存在从 到 的路径, 算法即可停止.

Dinic 算法得到的 是最大流, 且复杂度为 .

PROOF 算法终止时, 不存在从 到 的路径, 这意味着 的最大流为零, 于是 , 即 为 的最大流. 注意到每个阶段的 中的 都大于前一阶段的 , 而整张图中最长路径为 , 于是至多有 个阶段. 在每个阶段中, 需要做的事情包括构造 和计算 , 这在一次BFS中可以做到, 复杂度为 ; 接着需要计算极大流 , 包括删边和修改容量, 删边的次数显然为 次, 而对于修改容量, 由于 为有向无环图, 则推送最小 时至多推送 次, 每次推送修改容量至多修改 次, 于是工作为 , 因此每个阶段的复杂度为 , 于是最终的复杂度为 .