Edmonds-Karp

从S开始bfs，直到找到一条到达T的路径后将该路径增广，并重复这一过程。

在处理过程中，为了应对“找到的一条路径把其他路径堵塞”的情况，采用了建反向弧的方式来实现“反悔”过程。

这种“反悔”的想法和技巧值得借鉴。

 1 int maxFlow()
 2 {
 3     int ret = 0;
 4     for (;;)
 5     {
 6         memset(f, 0, sizeof f);
 7         memset(bck, 0, sizeof bck);
 8         std::queue<int> q;
 9         f[S] = INF, q.push(S);
10         for (int tmp; q.size(); )
11         {
12             tmp = q.front(), q.pop();
13             for (int i=head[tmp]; i!=-1; i=nxt[i])
14             {
15                 int v = edges[i].v;
16                 if (!f[v]&&edges[i].f < edges[i].c){
17                     f[v] = std::min(f[tmp], edges[i].c-edges[i].f);
18                     bck[v] = i, q.push(v);
19                 }
20             }
21             if (f[T]) break;
22         }
23         if (!f[T]) break;
24         for (int i=T; i!=S; i=edges[bck[i]].u)
25         {
26             edges[bck[i]].f += f[T];
27             edges[bck[i]^1].f -= f[T];
28         }
29         ret += f[T];
30     }
31     return ret;
32 }

Dinic

EK的效率是$O(nm^2)$的，它把很多时间浪费在了重复的搜索上面。

dinic有如下两个重要的定义：

层次$ ext{level(x)}$：表示点$x$在层次图中与源点$S$的距离。
层次图：在原来的残量网络当中，只保留所有可被增广的边以及与之相连的点。

bfs建出来的层次图对于接下去的dfs增广具有一种“指导”作用。使用了反向弧技巧，意味着不管用什么方法，只需要找到一条增广路就行。在这种情况下，我们来考虑dfs增广的优劣之处：一方面它一旦找到一条增广路就能快速退出，比bfs的逐级外扩更高效；另一方面纯粹的dfs受搜索顺序的影响很大，因为（可以像卡SPFA以及某些图论算法一样）挂一些诱导节点附带数量巨大的边，就能置dfs于死地。但是这里dfs依靠建出来的层次图，每次只向距离+1的点搜索。这意味着我们避免了对同一个节点的重复搜索，或是偏离T方向浪费时间。

 1 bool buildLevel()
 2 {
 3     memset(lv, 0, sizeof lv);
 4     std::queue<int> q;
 5     q.push(S), lv[S] = 1;
 6     for (int i=1; i<=T; i++) cur[i] = head[i];　　　//tip1
 7     for (int tmp; q.size(); )
 8     {
 9         tmp = q.front(), q.pop();
10         for (int i=head[tmp]; i!=-1; i=nxt[i])
11         {
12             int v = edges[i].v;
13             if (!lv[v]&&edges[i].f < edges[i].c){
14                 lv[v] = lv[tmp]+1, q.push(v);
15                 if (v==T) return true;　　　　　　　　//tip2
16             }
17         }
18     }
19     return false;
20 }
21 int fndPath(int x, int lim)　　　　　　　　//此处已更新，详情见下
22 {
23     if (x==T) return lim;
24     for (int &i=cur[x]; i!=-1; i=nxt[i])　　　　　　 //tip1
25     {
26         int v = edges[i].v, val;
27         if (lv[x]+1==lv[v]&&edges[i].f < edges[i].c){
28             if ((val = fndPath(v, std::min(lim, edges[i].c-edges[i].f)))){
29                 edges[i].f += val, edges[i^1].f -= val;
30                 return val;
31             }else lv[v] = -1;　　　　　　　　　　　　　//tip3　　
32         }
33     }
34     cur[x] = head[x];
35     return 0;
36 }
37 int dinic()
38 {
39     int ret = 0, val;
40     while (buildLevel())
41         while ((val = fndPath(S, INF))) ret += val;
42     return ret;
43 }

dinic有三个常见优化：

tip1当前弧优化：这个优化是针对边的，有些网络流的边数巨大。这个优化是为了确保在同一层次图的多次增广当中，可以实现“从上一次成功增广停下的地方再次开始”这一个功能。

tip2层次图优化：每次建层次图只需要达到T即可。

tip3堵塞点优化：姑且这么叫吧……在同一层次图下，一个点若未被增广则再也不会被增广了。

个人觉得tip3的效果最明显。tip1是为了少遍历一些边，但是节省的只不过是遍历（因为并不执行操作）的代价；tip2是看脸的优化；tip3应该算是强剪枝。

3.5upd：

今天写最大权闭合子图时候，才发现我学了个假的dinic.

当时是照着menci的 Dinic 学习笔记学的dinic，然而今天才发现，menci的指针小常数真的是非常人可比拟的……

就拿bzoj1497: [NOI2006]最大获利来说吧：同样的流程结构，我结构体写法用时7.5s；menci的指针版本只需要0.75s（本地不开O2），这比我加满优化（包括改成以下这个写法）都要快得多……

dinic需要多路优化，而非以上dfs提到的每次寻找到一条增广路就退出。

正经的板子：

 1 bool buildLevel()
 2 {
 3     std::queue<int> q;
 4     memset(lv, 0, sizeof lv);
 5     lv[S] = 1, q.push(S);
 6     for (int i=1; i<=T; i++) cur[i] = head[i];
 7     for (int tmp; q.size(); )
 8     {
 9         tmp = q.front(), q.pop();
10         for (int i=head[tmp]; i!=-1; i=nxt[i])
11         {
12             int v = edges[i].v;
13             if (!lv[v]&&edges[i].f < edges[i].c){
14                 lv[v] = lv[tmp]+1, q.push(v);
15                 if (v==T) return true;
16             }
17         }
18     }
19     return false;
20 }
21 int fndPath(int x, int lim)
22 {
23     int sum = 0;
24     if (x==T||!lim) return lim;
25     for (int i=cur[x]; i!=-1&&sum <= lim; i=nxt[i])
26     {
27         int v = edges[i].v, val;
28         if (lv[x]+1==lv[v]&&edges[i].f < edges[i].c){
29             if ((val = fndPath(v, std::min(lim-sum, edges[i].c-edges[i].f)))){
30                 edges[i].f += val, edges[i^1].f -= val;
31                 sum += val;
32             }else lv[v] = -1;
33         }
34　　　　　 if (lim==sum) break;　　　　　　　　//小trick的效果是玄学致命的
34     }
35     cur[x] = head[x];
36     return sum;
37 }
38 int dinic()
39 {
40     int ret = 0, val;
41     while (buildLevel())
42         while ((val = fndPath(S, INF))) ret += val;
43     return ret;
44 }