网络流很有用啊， 对于有些规则很复杂的图，很有可能就可以用网络流来求解。

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

初步，我们不考虑费用问题。
先按照正常的人类思维来考虑这个问题：

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;
    }
};