Front Push-Relabel Algorithm

接口定义

Input：容量数组vector<vector<int>> capacity ，大小为n；源点int source，汇点int sink；
Output：最大流int maxflow；

算法描述

数据结构

flow：n*n的二维数组，表示结点间的流量，flow[u][v]非零当且仅当capacity[u][v]非零。
excess：n维数组，表示结点的溢出流量。
height：n维数组，表示结点的高度。
L：除去源点和汇点后，其余结点组成的链表，遍历此链表进行discharge操作。
current：n维数组，表示结点u当前考虑推送的相邻结点。

算法步骤

初始化

源点高度设置为n，其余结点必须先尝试推送到所有其他结点，还有溢出的流才能将流返还源点。初始化链表L。遍历源点的所有相邻边，填满这些边的流量，并设置相邻结点的溢流。

// initialize data structure

int n = capacity.size();

vector<vector<int>> flow(n, vector<int>(n, 0));

vector<int> excess(n, 0);

vector<int> height(n, 0);

height[source] = n;

list<int> L;

for (int u = 0; u < n; u++) {

    if (u != source && u != sink) {

        L.push_back(u);

    }

}

vector<int> current(n, 0);

// initialize perflow

for (int v = 0; v < n; v++) {

    if (capacity[source][v] > 0) {

        flow[source][v] = capacity[source][v];

        excess[v] = capacity[source][v];

        excess[source] -= capacity[source][v];

    }

}

push操作

仅当结点u存在溢流，边(u,v)存在残留容量，且u的高度恰好比v的高度大1时（符合这一条件的边称为许可边），将多余流量尽可能从u推送到v。注意残留容量residual定义为：

若(u,v)是流网络的边，即容量非零，则等于剩余容量C[u][v] - F[u][v]；
否则，等于反向流量F[v][u]，表示允许将溢流倒回，降低边(v,u)的流量；

因此，除了修改两个结点的溢流外，还需分上面的两种情况修改边的流量。

void push(vector<vector<int>>& C, vector<vector<int>>& F, vector<int>& E, int u, int v) {

    int residual = C[u][v] > 0 ? C[u][v] - F[u][v] : F[v][u];

    int delta = min(E[u], residual);

    E[u] -= delta;

    E[v] += delta;

    if (C[u][v] > 0) {

        F[u][v] += delta;

    }

    else {

        F[v][u] -= delta;

    }

}

relabel操作

仅当结点u存在溢流，其不存在许可边。则将u的高度设置为其最低的存在残留容量的相邻结点的高度加1，使得它们之间的边成为许可边。

void relabel(vector<vector<int>>& C, vector<vector<int>>& F, vector<int>& H, int u) {

    int min_height = INT_MAX;

    for (int v = 0; v < C.size(); v++) {

        int residual = C[u][v] > 0 ? C[u][v] - F[u][v] : F[v][u];

        if (residual > 0) {

            min_height = min(min_height, H[v]);

        }

    }

    H[u] = min_height + 1;

}

discharge操作

反复尝试将结点u的溢流推送出去，直到结点u不存在溢流。使用current数组存储当前u考虑推送的目标，如果目标不可推送（非许可边），则考虑下一个邻接点。如果所有邻接点均尝试过且溢流仍然非零，则relabel，并重新将current指向头部。如果成功推送则不动current。

void discharge(vector<vector<int>>& C, vector<vector<int>>& F, vector<int>& E, vector<int>& H, vector<int>& current, int u) {

    while (E[u] > 0) {

        int v = current[u];

        if (v >= C.size()) {

            relabel(C, F, H, u);

            current[u] = 0;

        }

        else {

            int residual = C[u][v] > 0 ? C[u][v] - F[u][v] : F[v][u];

            if (residual > 0 && H[u] == H[v] + 1) {

                push(C, F, E, u, v);

            }

            else {

                current[u]++;

            }

        }

    }

}

算法主体

从链表L的头部开始discharge结点，如果将结点的溢流释放后高度发生了变化，则需要重新将结点放到表头并遍历其余结点进行释放。实际上这是为了保证链表中结点u之前的结点不存在溢流（relabel以后可能会将流倒回之前的结点），这样算法结束时链表中所有结点均不存在溢流。

结束时，源点的溢流应该等于最大流的相反数，这是因为源点没有流入只有流出，而流出的流量之和就等于最大流。

int getMaxFlow(vector<vector<int>> capacity, int source, int sink) {

    // initialize data structure

    int n = capacity.size();

    vector<vector<int>> flow(n, vector<int>(n, 0));

    vector<int> excess(n, 0);

    vector<int> height(n, 0);

    height[source] = n;

    list<int> L;

    for (int u = 0; u < n; u++) {

        if (u != source && u != sink) {

            L.push_back(u);

        }

    }

    vector<int> current(n, 0);

    // initialize perflow

    for (int v = 0; v < n; v++) {

        if (capacity[source][v] > 0) {

            flow[source][v] = capacity[source][v];

            excess[v] = capacity[source][v];

            excess[source] -= capacity[source][v];

        }

    }

    // relabel to front

    auto u = L.begin();

    while (u != L.end()) {

        int old_height = height[*u];

        discharge(capacity, flow, excess, height, current, *u);

        if (height[*u] > old_height) {

            int tmp = *u;

            L.erase(u);

            L.push_front(tmp);

            u = L.begin();

        }

        u++;

    }

    // compute max flow

    return -excess[source];

}

优化写法

可以简化residual的计算，允许数组flow存在负值，用来表示反向流量，这样残留容量residual可以统一成一个表达式：residual = C[u][v] - F[u][v]。相应的需要修改push操作，将ifelse去掉，增加当前方向的流量的同时，将反向流量减少，从而同时更新了反向边。

巴特西

最大流-前置push-relabel算法实现