graph | Max flow

最大流算法，解决的是从一个起点到一个终点，通过任何条路径能够得到的最大流量。

有个Edmond-Karp算法：

1. BFS找到一条增广路径；算出这条路径的最小流量（所有边的最小值）increase；

2. 然后更新路径上的权重（流量），正向边加上increase，反向边减去increase;

3. 重复1，直到没有增广路径；

可以证明的是在使用最短路增广时增广过程不超过V*E次，每次BFS的时间都是O(E)，所以Edmonds-Karp的时间复杂度就是O(V*E^2)。

图的BFS和DFS的时间复杂度都是O(n+e)，这里指用邻接表的方式。每次出栈或者出队列，都要扫一遍该点的所有边，所有点的边集加起来就是O(e)了。

至于为什么要用反向边，这里讲得挺清楚；

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <limits.h>

 #include <vector>

 using namespace std;

 class Maxflow {

     public:

         Maxflow() {}

         ~Maxflow() {

             if (pre) delete[] pre;

             if (flow) delete[] flow;

             if (weight) {

                 for (int i = ; i < vertices; ++i) {

                     delete[] weight[i];

                 }

                 delete[] weight;

             }

         }

         void readGraph(string filename) {

             freopen(filename.c_str(), "r", stdin);

             int edges;

             scanf("%d %d", &vertices, &edges);

             pre = new int[vertices];

             flow = new int[vertices];

             memset(flow, , vertices * sizeof(int));

             weight = new int*[vertices];

             for (int i = ; i < vertices; ++i) {

                 weight[i] = new int[vertices];

                 memset(weight[i], , vertices * sizeof(int));

             }

             for (int i = ; i < edges; ++i) {

                 int v1, v2, w;

                 scanf("%d %d %d", &v1, &v2, &w);

                 weight[v1 - ][v2 - ] = w;

             }

         }

         int maxFlow() {

             int start = , end = vertices - ;

             int max = ;

             int increase = ;

             while ((increase = bfs(start, end)) != ) {

                 int p = end;

                 while (p != start) {

                     int b = pre[p];

                     weight[b][p] -= increase;

                     weight[p][b] += increase;

                     p = b;

                 }

                 max += increase;

             }

             return max;

         }

     private:

         int bfs(int start, int end) {

             memset(pre, -, vertices * sizeof(int));

             vector<vector<int> > layers();

             int cur = , next = ;

             layers[cur].push_back(start);

             flow[start] = INT_MAX;

             while (!layers[cur].empty()) {

                 layers[next].clear();

                 for (int i = ; i < layers[cur].size(); ++i) {

                     int v1 = layers[cur][i];

                     for (int v2 = ; v2 < vertices; ++v2) {

                         if (weight[v1][v2] <=  || pre[v2] != -) continue;

                         pre[v2] = v1;

                         layers[next].push_back(v2);

                         flow[v2] = min(flow[v1], weight[v1][v2]);

                         if (v2 == end) return flow[v2];

                     }

                 }

                 cur = !cur;

                 next = !next;

             }

             return ;

         }

         int* pre;

         int** weight;

         int* flow;

         int vertices;

 };

 int main() {

     Maxflow maxflow;

     maxflow.readGraph("input.txt");

     cout<< maxflow.maxFlow() << endl;

     return ;

 }

sample input: