EK、Dinic和ISAP

79

网络流算法。Edmond-Karp,Dinic,ISAP的实现与性能分析
网络流很有用啊, 对于有些规则很复杂的图,很有可能就可以用网络流来求解。

首先,网络流是求在一个有向图中,边存在有流量限制也即容量(有些还存在费用问题)。给定一个起点,一个终点,求从起点到终点通过各种途径能传送的最大流量(在最小费用下的最大流量)。

初步,我们不考虑费用问题。
先按照正常的人类思维来考虑这个问题:
  1. 先把图画出来,然后从起点往终点连线;
  2. 连到不能连后再看有没有哪条路不走会得到更好的结果,对之前的结果加以调整;
  3. 计算出每条路径的流量值
  4. 得到出最大流。

可以看出,有一个很重要的过程就是,如果我们选择了一个路径,我们还需要一个后悔的途径。
于是,引入了反向边的概念。
如果我们从a流向b 100单位的流量,同时记录下从b流向a -100单位的流量。如果这条边的流量不应该用在这个路径上时,真正应该使用这条边流量的路径可以通过反向边来调整流量结果。


如果我们找到了从起点到终点的一条路径,我们应该如何计算流量?
计算路径上所有边容量的最小值,然后这些边的流量同时加上这个最小值。
这种每条路径慢慢往上增加流量的做法叫做增广路
可以得知,如果还存在一条路径,其容量减去流量的delta值不为0,那么总的流量还能再加上delta。




增广路反向边就是求解网络流问题的关键所在。

要实现反向边很容易,只需要在向图中插入(from,to,cap,flow)的边的同时插入(to,from,0,0)的边即可。
每次在给一条边增加流量的同时,给其对应边减少相应的流量

而实现增广路,可以通过找到起点到终点的最短路,然后使用前置节点数组从终点返回起点计算delta,最后再次从终点到起点增加流量。
而找最短路的方法则是使用BFS。
不断重复BFS,直到起点和终点不连通(流量等于容量时,这条路就不能走了),获得的流量值的和即是最大流。

将这个思路实现出来,就是Edmond-Karp
  1. 使用BFS找到增广路
  2. 根据前置节点获取Delta
  3. 更新这条路径的流量(包括反向边流量)
  4. 重复上面的过程,直到起点和终点不连通。




如果有一条起点到终点的路径,中间有很多分分合合的支路,那么使用Edmond-Karp将会把大量的时间用在BFS找最短路上。
很可能上一次已经找到了一条增广路,下一条增广路其实只需要退一步换个方向即可,但是在Edmond-Karp里仍然要跑一次BFS。
而这种“退一步,换个方向走”则很容易联想到DFS。

Dinic则是使用BFS分层(计算每个节点到起点的位置),然后使用DFS一层一层往下走,找增广路,找到后返回上一层继续往下找,直到该节点往后没有增广路,进行下一次BFS。
这里有一个当前弧优化,在返回上一层继续往下找时,其实可以直接从上一条路径的下一条路径开始找就行,没有必要从第一条开始找。
在图很复杂的时候,这里可以省下大量的时间。

将Dinic的算法实现就是:
  1. 根据BFS分层
  2. 根据分层结果进行DFS
  3. 保证按照层次往后进行DFS,来寻找增广路
  4. 找到增广路后,返回上一层,并且从当前路径的下一条路径继续找增广路。
  5. 当DFS找不到新的增广路后,再次进行新的BFS分层
  6. 当起点和终点不联通时结束程序

相关代码可以见poj 1273



那么又可以发现,我已经DFS了,是不是DFS的同时也可以做一部分BFS的工作,甚至完全替代掉BFS呢?
每次找到出度为0的节点的时候,就地更新分层来替代BFS的工作,这样就成为了ISAP算法。

如果某一层的节点数目为0,说明起点到终点不连通,可以直接结束,这是GAP优化

因此ISAP是一种对Dinic的进一步优化,两者时间复杂度是一样的,但是结合上各种剪枝优化,以及省去BFS的常数优化,其时间性能远好于Dinic。

思路如下:
  1. 先进行一次BFS预分层(到终点到的距离)
  2. 统计各层的节点个数(GAP优化用)
  3. DFS遍历找增广路。
  4. 如果找到增广路,则按照之前的算法计算。
  5. 如果找不到能走的路径,则更新当前点的层数为周围能到达节点的最小值+1(这里不能走是因为不符合分层的走法,但是其实还是存在通路的。如果完全不存在通路,直接把距离设置成最大,这个点已经没有再考虑的必要了),然后返回上一层,继续往后找增广路(当前弧优化)
  6. 如果发现有一层的点数为0,则结束程序(GAP优化)
  7. 直到从起点到终点找不到任何路径,结束程序。

其中,ISAP的DFS改为循环写法, 可以进一步优化常数。

下面是一个ISAP模板。
class maxFlow {
    struct Edge {
        int cap, flow;
        Edge(int _cap = 0, int _flow = 0) : cap(_cap), flow(_flow) {}
    };
    static const int INF = 0x7FFFFFFF;
    static const bool DEBUG = false;
    int s, v, n;

    Edge **edges;
    int *dis, *num, *pre, *cur;

  public:
    void addEdge(int from, int to, int cap) {
        edges[from][to].cap += cap;
    }

    int ISAP() {
        bfs();
        layerCalc();
        return dfs();
    }
    maxFlow(int s, int v, int n) {
        this->s = s;
        this->v = v;
        this->n = n;

        edges = new Edge *[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new Edge[n];
            memset(edges[i], 0, sizeof(Edge) * n);
        }

        dis = new int[n];
        num = new int[n + 1];
        pre = new int[n];
        cur = new int[n];
    }
    ~maxFlow() {
        for (int i = 0; i < n; ++i)
            delete[] edges[i];
        delete[] edges;

        delete[] dis;
        delete[] num;
        delete[] pre;
        delete[] cur;
    }

  private:
    queue<int> Q;

    void bfs() {
        while (!Q.empty())
            Q.pop();
        memset(dis, 0, sizeof(int) * n);
        Q.push(v);
        dis[v] = 1;
        while (!Q.empty()) {
            int t = Q.front();
            Q.pop();
            for (int i = 0; i < n; ++i) {
                Edge &e = edges[i][t];
                if (e.cap > e.flow && !dis[i]) {
                    dis[i] = dis[t] + 1;
                    Q.push(i);
                }
            }
        }
    }

    void layerCalc() {
        memset(num, 0, sizeof(int) * (n + 1));
        for (int i = 0; i < n; ++i)
            ++num[dis[i]];
    }

    int Augumemt() {
        int t = v, delta = INF;
        while (t != s) {
            int &lastNode = pre[t];
            Edge &e = edges[lastNode][t];
            delta = min(delta, e.cap - e.flow);
            t = lastNode;
        }
        t = v;
        while (t != s) {
            int &lastNode = pre[t];
            Edge &e = edges[lastNode][t];
            Edge &e2 = edges[t][lastNode];
            e.flow += delta;
            e2.flow -= delta;
            t = lastNode;
        }
        return delta;
    }

    int dfs() {
        memset(pre, 0, sizeof(int) * n);
        memset(cur, 0, sizeof(int) * n);

        int flow = 0;
        int t = s;

        while (dis[s] <= n) {
            if (t == v) {
                flow += Augumemt();
                t = s;
            }

            int finish = true;
            for (int i = cur[t]; i < n; ++i) {
                Edge &e = edges[t][i];
                if (e.cap > e.flow && dis[t] == dis[i] + 1) {
                    finish = false;
                    pre[i] = t;
                    cur[t] = i;
                    t = i;
                    break;
                }
            }

            if (finish) {
                int m = n;
                for (int i = 0; i < n; i++) {
                    Edge &e = edges[t][i];
                    if (e.cap > e.flow)
                        m = min(m, dis[i]);
                }
                if (--num[dis[t]] == 0)
                    break;
                ++num[dis[t] = m + 1];
                cur[t] = 0;
                if (t != s)
                    t = pre[t];
            }
        }
        return flow;
    }
};
发布评论
  • 点击查看/关闭被识别为广告的评论