网络流入门

基本概念(从书上摘抄,可以直接跳过不看)

容量网络和网络最大流

** 容量网络: ** 设 G(V, E)是一个有向网络, 在 V 中指定了一个顶点, 称为源点(记为 Vs ), 以及另一个顶点, 称为汇点(记为 Vt); 对于每一条弧 <u, v>∈E, 对应有一个权值 c(u, v)>0, 称为弧的容量, 通常把这样的有向网络 G 称为容量网络。

也就是指: 一个拥有源点、汇点并且可以容纳流量的图.

** 弧的流量: ** 通过容量网络 G 中每条弧 <u, v> 上的实际流量(简称流量), 记为 f(u, v)。
** 网络流: ** 所有弧上流量的集合 f = { f(u, v) },称为该容量网络 G 的一个网络流。
** 可行流: ** 在容量网络 G(V, E) 中, 满足以下条件的网络流 f, 称为可行流:

** 弧流量限制条件: ** $ 0 ≤ f(u, v) ≤ c(u, v)$
** 平衡条件: ** 除了 Vs, Vt 外, 其余的点流入的流量总和等于流出的流量总和, 其中 Vs 流出的流量总和 - 流出的流量总和 = f, Vt 流入的流量总和 - 流出的流量总和 = f, 并且称 f 为可性流的流量.

也就是指: 在图中有一条从 Vs 到 Vt 的路径, 这条路径上起点 $f_o - f_i = f$, 终点 $f_i - f_o = f$，其他的点 $f_i == f_o$, 并且所有的边的当前流量小于等于最大流量.(其中 $f_i$ 代表流入流量, $f_o$ 代表流出流量)

** 伪流: ** 如果一个网络流只满足弧流量限制条件, 不满足平衡条件, 则这种网络流称为伪流, 或称为容量可行流。
** 最大流: ** 在容量网络 G(V, E) 中, 满足弧流量限制条件和平衡条件、且具有最大流量的可行流, 称为网络最大流, 简称最大流。

链与增广路

在容量网络 G(V, E) 中, 设有一可行流 f = { f(u, v) }, 根据每条弧上流量的多少、以及流量和容量的关系,可将弧分四种类型:

饱和弧, 即 $f(u, v) = c(u, v)$;
非饱和弧,即 $f(u, v) < c(u, v)$;
零流弧, 即 $f(u, v) = 0$;
非零流弧, 即 $f(u, v) > 0$。

** 链: ** 在容量网络中,称顶点序列$(u, u_1, u_2, …, u_n, v)$为一条链,要求相邻两个顶点之间有一条弧, 如 <u, u1> 或 <u1, u> 为容量网络中一条弧。沿着 Vs 到 Vt 的一条链, 各弧可分为两类:

** 前向弧: ** 方向与链的正方向一致的弧, 其集合记为 P+;
** 后向弧: ** 方向与链的正方向相反的弧, 其集合记为 P-;

** 增广路: ** 设 f 是一个容量网络 G 中的一个可行流, P 是从 Vs 到 Vt 的一条链, 若 P 满足下列条件:

在 P 的所有前向弧 <u, v> 上, $0 ≤ f(u, v) < c(u, v)$, 即 P+ 中每一条弧都是非饱和弧;
在 P 的所有后向弧 <u, v> 上, $0 < f(u, v) ≤ c(u, v)$, 即 P– 中每一条弧是非零流弧。

则称 P 为关于可行流 f 的一条增广路, 简称为 增广路(或称为增广链、可改进路)。沿着增广路改进可行流的操作称为增广

残留容量与残留网络

** 残留容量: ** 给定容量网络 G(V, E) 及可行流 f, 弧 <u, v> 上的残留容量记为 $c’(u, v)=c(u, v)–f(u, v)$。每条弧的残留容量表示该弧上可以增加的流量。因为从顶点 u 到顶点 v 流量的减少, 等效于顶点 v 到顶点 u 流量增加, 所以每条弧 <u, v> 上还有一个反方向的残留容量 $c’(v, u) =– f(u, v)$。

一个容量网络中还可以压入的流量称为残留容量

** 残留网络: ** 设有容量网络 G(V, E) 及其上的网络流 f,G 关于 f 的残留网络(简称残留网络)记为 G'(V', E'), 其中 G’的顶点集 V’和 G 的顶点集 V 相同,即 V’=V, 对于 G 中的任何一条弧 <u, v>, 如果 $f(u, v) < c(u, v)$, 那么在 G’中有一条弧 <u, v>∈E', 其容量为 $c’(u, v) = c(u, v) – f(u, v)$, 如果 $f(u, v) > 0$,则在 G’中有一条弧 <v, u>∈E', 其容量为 $c’(v, u) = f(u, v)$, 残留网络也称为剩余网络.

由残留的容量以及源点汇点构成的网络。

割与最小割

** 割: ** 在容量网络 G(V, E) 中, 设 E'⊆E, 如果在 G 的基图中删去 E’ 后不再连通, 则称 E’ 是 G 的割。割将 G 的顶点集 V 划分成两个子集 S 和 T = V - S。将割记为(S, T)。
** s-t 割: ** 更进一步, 如果割所划分的两个顶点子集满足源点 Vs ∈ S,汇点 Vt ∈ T, 则称该割为 s-t 割。 s-t 割(S, T)中的弧 <u, v>(u∈S, v∈T) 称为割的前向弧, 弧 <u, v>( u∈T, v∈S) 称为割的反向弧。
** 割的容量: ** 设 (S, T) 为容量网络 G(V, E) 的一个割, 其容量定义为所有前向弧的容量总和, 用 c(S, T) 表示。
** 最小割: ** 容量网络 G(V, E) 的最小割是指容量最小的割。

最大流

最大流相关算法有两种解决思想, 一种是增广路算法思想, 另一种是预流推进算法思想。下面将分别介绍这两种算法思想。

增广路算法(Ford-Fulkerson)

基本思想

根据增广路定理, 为了得到最大流, 可以从任何一个可行流开始, 沿着增广路对网络流进行增广, 直到网络中不存在增广路为止,这样的算法称为增广路算法。问题的关键在于如何有效地找到增广路, 并保证算法在有限次增广后一定终止。
增广路算法的基本流程是 :

(1) 取一个可行流 f 作为初始流(如果没有给定初始流,则取零流 f= { 0 }作为初始流);
(2) 寻找关于 f 的增广路 P,如果找到,则沿着这条增广路 P 将 f 改进成一个更大的流, 并建立相应的反向弧;
(3) 重复第(2)步直到 f 不存在增广路为止。

图示如下:

增广路算法的关键是 寻找增广路 和 改进网络流。
** 问题: 为什么要创建反向弧呢? **
** 原因: 为程序提供一次反悔的机会 ** 什么意思, 如下图所示:
在图中如果程序找到了一条增广路 1 -> 2 -> 4 -> 6, 此时得到一个流量为 2 的流并且无法继续进行增广,
但是如果在更新可行流的同时建立反向弧的话, 就可以找到 1 -> 3 -> 4 -> 2 -> 5 -> 6 的可行流, 流量为1, 这样就可以得到最大流为 3.

一般增广路算法(EdmondsKarp)

算法流程

在一般的增广路算法中, 程序的实现过程与增广路求最大流的过程基本一致. 即每一次更新都进行一次找增广路然后更新路径上的流量的过程。但是我们可以从上图中发现一个问题, 就是每次找到的增广路曲曲折折非常长, 此时我们往往走了冤枉路(即：明明我们可以从源点离汇点越走越进的，可是中间的几条边却向离汇点远的方向走了), 此时更新增广路的复杂度就会增加。EK 算法为了规避这个问题使用了 bfs 来寻找增广路, 然后在寻找增广路的时候总是向离汇点越来越近的方向去寻找下一个结点。

算法实现

邻接矩阵

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 300;
const int MAX_INT = ((1 << 31) - 1);

int n;                                      // 图中点的数目
int pre[MAXN];                              // 从 s - t 中的一个可行流中, 节点 i 的前序节点为 Pre[i];
bool vis[MAXN];                             // 标记一个点是否被访问过
int mp[MAXN][MAXN];                         // 记录图信息

bool bfs(int s, int t){
    queue <int> que;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    pre[s] = s;
    vis[s] = true;
    que.push(s);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = 1; i <= n; i++){
            if(mp[u][i] && !vis[i]){
                pre[i] = u;
                vis[i] = true;
                if(i == t) return true;
                que.push(i);
            }
        }
    }
    return false;
}

int EK(int s, int t){
    int ans = 0;
    while(bfs(s, t)){
        int mi = MAX_INT;
        for(int i = t; i != s; i = pre[i]){
            mi = min(mi, mp[pre[i]][i]);
        }
        for(int i = t; i != s; i = pre[i]){
            mp[pre[i]][i] -= mi;
            mp[i][pre[i]] += mi;
        }
        ans += mi;
    }
    return ans;
}

邻接表

const int MAXN = 430;
const int MAX_INT = (1 << 30);

struct Edge{
    int v, nxt, w;
};

struct Node{
    int v, id;
};

int n, m, ecnt;
bool vis[MAXN];
int head[MAXN];
Node pre[MAXN];
Edge edge[MAXN];

void init(){
    ecnt = 0;
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

bool bfs(int s, int t){
    queue <int> que;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    pre[s].v = s;
    vis[s] = true;
    que.push(s);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = head[u]; i + 1; i = edge[i].nxt){
            int v = edge[i].v;
            if(!vis[v] && edge[i].w){
                pre[v].v = u;
                pre[v].id = i;
                vis[v] = true;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return false;
}

int EK(int s, int t){
    int ans = 0;
    while(bfs(s, t)){
        int mi = MAX_INT;
        for(int i = t; i != s; i = pre[i].v){
            mi = min(mi, edge[pre[i].id].w);
        }
        for(int i = t; i != s; i = pre[i].v){
            edge[pre[i].id].w -= mi;
            edge[pre[i].id ^ 1].w += mi;
        }
        ans += mi;
    }
    return ans;
}

// 加边
addEdge(u, v, w);
addEdge(v, u, 0);
// 调用
int ans = EK(s, t);

算法复杂度

每进行一次增广需要的时间复杂度为 bfs 的复杂度 + 更新残余网络的复杂度, 大约为 O(m)(m为图中的边的数目), 需要进行多少次增广呢, 假设每次增广只增加1, 则需要增广 nW 次(n为图中顶点的数目, W为图中边上的最大容量), .

Dinic 算法

算法思想

DINIC 在找增广路的时候也是找的最短增广路, 与 EK 算法不同的是 DINIC 算法并不是每次 bfs 只找一个增广路, 他会首先通过一次 bfs 为所有点添加一个标号, 构成一个层次图，然后在层次图中寻找增广路进行更新。

算法流程

利用 BFS 对原来的图进行分层，即对每个结点进行标号，这个标号的含义是当前结点距离源点的最短距离(假设每条边的距离都为1)，注意：构建层次图的时候所走的边的残余流量必须大于0

用 DFS 寻找一条从源点到汇点的增广路, 注意: 此处寻找增广路的时候要按照层次图的顺序, 即如果将边(u, v)纳入这条增广路的话必须满足$dis[u] = dis[v] - 1$, 其中 $dis[i]$为结点 $i$的编号。找到一条路后要根据这条增广路径上的所有边的残余流量的最小值$l$更新所有边的残余流量(即正向弧 - l, 反向弧 + l).

重复步骤 2, 当找不到一条增广路的时候, 重复步骤 1, 重新建立层次图, 直到从源点不能到达汇点为止。

算法流程如下图所示:

算法实现

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 510;
const int MAXN_INT = (1 << 29);

int n, m;
int dis[MAXN];
int mp[MAXN][MAXN];

int bfs(int s){
    memset(dis, 0xff, sizeof(dis));
    dis[s] = 0;
    queue <int> que;
    que.push(s);
    while(!que.empty()){
        int top = que.front();
        que.pop();
        for(int i = 1; i <= n; i++){
            if(dis[i] < 0 && mp[top][i] > 0){
                dis[i] = dis[top] + 1;
                que.push(i);
            }
        }
    }
    if(dis[n] > 0) return true;
    return false;
}

int Find(int x, int low){
    int a = 0;
    if(x == n) return low;
    for(int i = 1; i <= n; i++){
        if(mp[x][i] > 0 
            && dis[i] == dis[x] + 1
            && (a = Find(i, min(low, mp[x][i])))){
            mp[x][i] -= a;
            mp[i][x] += a;
            return a;
        }
    }
    return 0;
}

int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        memset(mp, 0, sizeof(mp));
        int u, v, w;
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &w);
            mp[u][v] += w;
        }
        int ans = 0, tmp;
        while(bfs(1)){
            while(tmp = Find(1, MAXN_INT))
                ans += tmp;
        }
        printf("%d\n", ans);
    }
    return 0;
}

** 当前弧优化和多路增广:**

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 101000;
const int MAXN_INT = (1 << 29);

struct Edge{
    int v, w, nxt;
};

int s, t;
int n, m, ecnt;
Edge edge[MAXN * 2];
int head[MAXN], dis[MAXN], curEdge[MAXN];

void init(){
    ecnt = 0;
    memset(dis, -1, sizeof(dis));
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

int bfs(){
    dis[t] = 0;
    queue <int> que;
    que.push(t);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = head[u]; i + 1; i = edge[i].nxt){
            if(dis[edge[i].v] == -1 && edge[i ^ 1].w > 0){
                dis[edge[i].v] = dis[u] + 1;
                que.push(edge[i].v);
            }
        }
    }
    return dis[s] != -1;
}

int dfs(int u, int v, int flow){
    if(u == t) return flow;
    int delta = flow;
    for(int &i = curEdge[u]; i + 1; i = edge[i].nxt){
        if(dis[u] == dis[edge[i].v] + 1 && edge[i].w){
            int d = dfs(edge[i].v, v, min(delta, edge[i].w));
            edge[i].w -= d, edge[i ^ 1].w += d;
            delta -= d;
            if(delta == 0) break;
        }
    }
    return flow - delta;
}

int dinic(){
    int ans = 0;
    while(bfs()){
        for(int i = 0; i < n; i++)
            curEdge[i] = head[i];
        ans += dfs(s, t, MAXN_INT);
    }
    return ans;
}

int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        init();
        int u, v, w;
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, 0);
        }
        printf("%d\n", dinic());
    }
    return 0;
}

时间复杂度

$O(V^2E)

最短增广路算法(SAP)

算法思想

最短增广路算法是一种运用距离标号使寻找增广路的时间复杂度下降的算法。所谓的距离标号就是某个点到汇点的最少的弧的数量(即当边权为1时某个点的最短路径长度). 设点i的标号为d[i], 那么如果将满足d[i] = d[j] + 1, 且增广时只走允许弧, 那么就可以达到”怎么走都是最短路”的效果. 每个点的初始标号可以在一开始用一次从汇点沿所有反向的BFS求出.

算法流程

定义节点的标号为到汇点的最短距离;

每次沿可行边进行增广, 可行边即: 假设有两个点 i, j 若 d[i] = 3, d[j] = 4, 则d[j] = d[i] + 1, 也就是从 j 到 i 有一条边.

找到增广路后，将路径上所有边的流量更新.

遍历完当前结点的可行边后更新当前结点的标号为 $d[now] = min(d[next] | Flow(now, next) > 0) + 1$，使下次再搜的时候有路可走。

图中不存在增广路后即退出程序，此时得到的流量值就是最大流。

需要注意的是, 标号的更新过程首先我们要理解更新标号的目的。标号如果需要更新，说明在当前的标号下已经没有增广路可以继续走，这时更新标号就可以使得我们有继续向下走的可能，并且每次找的都是能走到的点中标号最小的那个点，这样也使得每次搜索长度最小.
下面的图演示了标号的更新过程:

首先我们假设有个图如下，为了简化没有标箭头也没有写流量:
为图标号, 每个点的标号为其到汇点的最短距离(这里把每条边看作1)
第一遍遍历时，找到了1->2->9这样一条增广路以后，更新边上流量值, 得到下图
棕色字体为边上的流量值。这时按照标号再搜一遍,发现从1出发已经找不到增广路了，因为flow(1,2)等于0不可以走，$ h[1]=2,h[3]=2≠h[1]+1,h[5]=4≠h[1]+1 $，所以这时更新1的标号，按照 $min(h[next]|Flow(now,next)>0)+1$，修改后 $h[1]=h[3]+1=3$.
第二遍遍历以后找到了这样一条增广路：1->3->4->9,做完这条路以后又发现无法找到可行边了，这时再更新标号使图中有路可走，如上文所说的那样做，再次修改后$h[1]=h[5]+1=5$，就这样搜索并更新直到变成下图
这时再更新h[1]发现没有点可以用来更新h[1]了，于是此时$h[1]=∞$，使程序退出。

** GAP 优化: ** 由于可行边定义为：$ (now, next) | h[now] = h[next]+1 $，所以若标号出现“断层”即有的标号对应的顶点个数为0，则说明剩余图中不存在增广路，此时便可以直接退出，降低了无效搜索。举个栗子：若结点标号为3的结点个数为0，而标号为4的结点和标号为2的结点都大于 0,那么在搜索至任意一个标号为4的结点时，便无法再继续往下搜索，说明图中就不存在增广路。此时我们可以以将$ h[1] = n$形式来变相地直接结束搜索

算法实现

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5010;
const int MAXN_INT = (1 << 29);

struct Edge{
    int v, w, nxt;
};

bool isFind;
int head[MAXN];
Edge edge[MAXN];
int dis[MAXN], gap[MAXN];
int n, m, ecnt, aug, maxFlow;


void init(){
    ecnt = maxFlow = 0;
    memset(gap, 0, sizeof(gap));
    memset(dis, 0, sizeof(dis));
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
    gap[0] = n;
}

void addEdge(int u, int v, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

void Find(int s){
    int dx, augc, minDis;
    if(s == n){
        isFind = true;
        maxFlow += aug;
        return;
    }

    augc = aug;
    minDis = n - 1;
    for(int i = head[i]; i + 1; i = edge[i].nxt){
        if(edge[i].w > 0){
            if(dis[s] == dis[edge[i].v] + 1){
                aug = min(aug, edge[i].w);
                Find(edge[i].v);
                if(dis[1] >= n) return;
                if(isFind){
                    dx = i;
                    break;
                }
                aug = augc;
            }
            minDis = min(minDis, dis[edge[i].v]);
        }
    }
    if(!isFind){
        gap[dis[s]]--;
        if(gap[dis[s]] == 0) dis[1] = n;
        dis[s] = minDis + 1;
        gap[dis[s]]++;
    }else{
        edge[dx].w -= aug;
        edge[dx ^ 1].w += aug;
    }
}

int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        init();
        int u, v, w;
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, 0);
        }

        while(dis[1] < n){
            isFind = 0;
            aug = MAXN_INT;
            Find(1);
        }
        cout << maxFlow << endl;
    }
    return 0;
}

时间复杂度

$O(V^2E)$

预流推进算法

预流推进算法是从一个预流出发对活跃顶点沿着允许弧进行流量增广,每次增广称为一次推进。在推进过程中,流一定满足流量限制条件,但一般不满足流量平衡条件, 因此只是一个伪流。此外, 如果一个伪流中, 从每个顶点(除源点 V s 、汇点 V t 外)流出的流量之和总是小于等于流入该顶点的流量之和, 称这样的伪流为预流。因此这类算法被称为预流推进算法。

算法流程

首先用一边 BFS 为图中每个顶点一个标号dis[v], 表示该点到v的最短路.

将与 S 相连的边设为满流, 并将这时产生的活动结点加入队列Q。

选出 Q 的一个活动结点 u 并依次判断残量网咯 G’ 中每条边(u, v), 若 $dis[u] = min(dis[v] + 1)$, 则顺着这些边推流, 直到 Q 变成非活动结点(不存在多余流量).

如果 u 还是活动结点，则需要对 u 进行重新标号: $dis[u] = min(dis[v] + 1)$, 其中边 (u, v) 存在于 G’ 中,然后再将 u 加入队列。

重复3, 4两个步骤直到队列 Q 为空。

算法实现

const int size = 501;
const int MAX = 1 << 15;
 
int graph[size][size];
int label[size];        //标号
bool visited[size];
 
bool bfs(int st, int ed)
{
    memset(label, -1, sizeof(label));
    memset(visited, false, sizeof(visited));
    label[st] = 0;
    visited[st] = true;
    vector < int >plist;
    plist.push_back(st);
    while (plist.size()) {
    int p = plist[0];
    plist.erase(plist.begin());
    for (int i = 0; i < size; i++) {
        if (graph[i][p] > 0 && !visited[i]) {
        plist.push_back(i);
        visited[i] = true;
        label[i] = label[p] + 1;
        }
    }
    }
    if (label[ed] == -1) {
    return false;
    }
    return true;
}
 
int inflow[size];       //流入量
 
int maxFlow()
{
    memset(inflow, 0, sizeof(inflow));
 
    //hights
    bfs(size - 1, 0);       //end point: size - 1, start point: 0
    memset(visited, false, sizeof(visited));
 
//prepare()
    vector < int >plist;
    for (int i = 0; i < size; i++) {
    if (graph[start][i] > 0) {
        inflow[i] = graph[start][i];
        graph[start][i] -= inflow[i];
        graph[i][start] += inflow[i];
        if (!visited[i]) {
        plist.push_back(i);
        visited[i] = true;
        }
    }
    }
    while (plist.size()) {
    int p = plist[0];
    plist.erase(plist.begin());
    visited[p] = false;
    int minLabel = -1;
    for (int i = 0; i < size; i++) {
        if (graph[p][i] > 0) {
        if (label[p] == label[i] + 1) {
            int flow = min(inflow[p], graph[p][i]);
            inflow[p] -= flow;
            inflow[i] += flow;
            graph[p][i] -= flow;
            graph[i][p] += flow;
 
            if (!visited[i] && inflow[i] > 0) {
            plist.push_back(i);
            visited[i] = true;
            }
        }
        }
    }
    if (inflow[p] > 0 && p != end) {
        for (int i = 0; i < size; i++) {
        if (graph[p][i] > 0) {
            if (minLabel == -1 || minLabel > label[i] + 1) {
            minLabel = label[i] + 1;
            }
        }
        }
        if (!visited[p] && minLabel != -1 && minLabel < size)    //minLabel < size, 这个条件需要加上, 因为经过测试发现有死循环的可能
        {
        for (int i = 0; i < size; i++) {
            if (label[i] + 1 == minLabel && graph[p][i] > 0) {
            visited[p] = true;
            label[p] = minLabel;
            plist.push_back(p);
            break;
            }
        }
        }
    }
    }
    return inflow[end];
}

复杂度分析

如果该算法的Q是标准的FIFO队列，则时间复杂度为$(n^2m)$，最高标号不会超过$n$（超过时必无到汇的路径），所以$n$个点每个最多重新标号$n$次，两次标号之间$m$条边每条最多推流一次。如果是优先队列，并且标号最高的点优先的话，我们就得到了最高标号预流推进算法，其时间复杂度仅为$n^2\sqrt{m}$.

最小费用最大流

简介

最小费用最大流是解决这么一种问题: 对于图中的每一条边来说, 除了有一个最大容量的属性以外，还有一个费用属性, 即流过这条边的单位流量的花费。求解的问题为在保证从源点到汇点的流量最大的前提下使得花费最少。

求解思想

我们来考虑这么一个问题: 在最短路的一些变形的题目中往往有这种题，每条路不仅仅有一个长度还有一个建设的费用，最终求从起点到终点在保证路最短的前提下，使得花费的钱最少。当时我们是怎么求解的呢？
首先我们知道，最短路的长度是一定的，但是组成一条最短路的边是不一定的，所以我们在搜索这条最短路的时候只要通过调整待选边的优先级来控制搜索的方向就可以满足上述问题的要求。
这个问题跟我们现在求解的最小费用最大流问题神似啊，只要我们在寻找增广路的时候调整待选边的优先级来控制寻找方向，这个问题就可以解决了啊。我们直到对于一条增广路来说, 花费满足: $cost = minFlow * \sum w_i(i\in 增广路上的边)$, 实际上这里的优先级就是每条边的长度认为是其单位流量的花费的最短路。

求解算法

基于最大流的三种算法，求解最小费用最大流也具有三种算法，我们来对比一下这三对算法:

** 最大流 EK 算法:** 每次用广搜寻找一条最短的增广路（即包含最少的边），然后沿其增广。
** 费用流 E’K’ 算法:** 每次用spfa计算图的距离标号，然后沿着可行边进行增广。

** 最大流 DINIC 算法:** 用广搜获得每个点到源点的距离标号，增广时沿距离标号严格减1的路径增广，直到网络中不再存在这么一条路径，那么重新广搜计算距离标号，如果广搜发现整个源点到汇点已经不连通那么退出算法。
** 费用流原始对偶算法:** 用 SPFA 获得每个点到源点的最短路，增广时沿着最短路前进的方向增广, 直到网络中不存在一条路径时重新 SPFA 求最短路, 直到没有一条最短路可以到达汇点为止。

** 最大流 SAP 算法:** 与 dinic 一样基于距离标号，不过这里保存的是到汇点的距离标号。并且考虑每次增广对网络的影响，发现增广只会使点的距离标号变大，并且并不会破坏距离标号 $dis[u] <= dis[v] + w[u, v]$ 的性质，只会使得等号不再成立。找不到可行边就是因为没有一个结点v使得$dis[u] == dis[v] + w[u, v]$。那么重新使等号成立的方法也很简单，并不需要重新计算整个图的距离标号，只需要调整距离标号：如果从u点开始寻找增广路没有成功，即没有一个v使得$dis[u] == dis[v] + w[u, v]$那么在所有<u,v>（v∈V）中找到距离标号最小的一个v，使$dis[u] = dis[v] + w[u, v]$即可。
** 费用流 ZKW 算法:** 每次增广，同样不会破坏距离标号$dis[u] <= dis[v] + w[u, v]$，只会使得等号不再成立。并且被破坏的点并没有很多（只有在增广路上的点有可能被破坏）。因此并不需要SPFA来重新计算全部的距离标号。如果某一次寻找可行边组成增广路的尝试进行到点u失败，那么在所有的边$<u,v>（v∈V$中找到距离标号最小的一个v，使$dis[v] == dis[v] + w[u, v]&成立即可。

费用流 E’K’ 算法

思想上面说过了, 就是把最大流 EK 算法里面的 bfs 替换为 SPFA, 改变遍历的优先级来实现:

算法步骤

与 EK 算法相同, 只不过将 bfs 换成 spfa求最短路, 边权为该边的单位流量花费.
如下图所示

算法实现

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
const int MAXM = 1000100;
const int MAXN_INT = (1 << 29);

struct Edge{
    int v, w, c, nxt;
};

struct Node{
    int id, v;
};

bool vis[MAXN];
Node pre[MAXN];
Edge edge[MAXN];
int n, m, ecnt, sumFlow;
int head[MAXN], dis[MAXN];

void init(){
    ecnt = 0;
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int c, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].c = c;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

bool SPFA(int s, int t, int n){
    queue <int> que;
    memset(vis, 0, sizeof(vis));
    fill(dis, dis + MAXN, MAXN_INT);
    vis[s] = true;
    dis[s] = 0;
    que.push(s);
    while(!que.empty()){
        int u =que.front();
        que.pop();
        vis[u] = false;
        for(int i = head[u]; i + 1; i = edge[i].nxt){
            int v = edge[i].v;
            if(edge[i].c && dis[v] > dis[u] + edge[i].c){
                dis[v] = dis[u] + edge[i].c;
                pre[v].v = u;
                pre[v].id = i;
                if(!vis[v]){
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    if(dis[t] == MAXN_INT) return false;
    return true;
}

int MCMF(int s, int t, int n){
    int flow = 0;
    int minCost = 0;
    while(SPFA(s, t, n)){
        int minFlow = MAXN_INT + 1;
        for(int i = t; i != s; i = pre[i].v){
            minFlow = min(minFlow, edge[pre[i].id].w);
        }

        for(int i = t; i != s; i = pre[i].v){
            edge[pre[i].id].w -= minFlow;
            edge[pre[i].id ^ 1].w += minFlow;
        }
        minCost += dis[t] * minFlow;
    }
    sumFlow = flow;
    return minCost;
}

int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        int u, v, c, w;
        for(int i = 0; i < m; i++){
            scanf("%d%d%d%d", &u, &v, &c, &w);
            addEdge(u, v, c, w);
            addEdge(v, u, -c, 0);
        }
        int ans = MCMF(1, n, n);
        printf("%d\n", ans);
    }
    return 0;
}

基本概念(从书上摘抄,可以直接跳过不看)

容量网络和网络最大流

链与增广路

残留容量与残留网络

割与最小割

相关定理

残留网络与原网络的关系

网络流流量与割的净流量之间的关系

网络流流量与割的容量之间的关系

最大流最小割定理

增广路定理

几个等价命题

最大流

增广路算法(Ford-Fulkerson)

基本思想

一般增广路算法(EdmondsKarp)

算法流程

算法实现

邻接矩阵

邻接表

算法复杂度

Dinic 算法

算法思想

算法流程

算法实现

时间复杂度

最短增广路算法(SAP)

算法思想

算法流程

算法实现

时间复杂度

预流推进算法

算法流程

算法实现

复杂度分析

最小费用最大流

简介

求解思想

求解算法

费用流 E’K’ 算法

算法步骤

算法实现