最大流-Dinic算法和SAP算法简介

求解最大流一般采用两种思路，一种是预流，另一各是增广路。增广路这种思想是基于以下定理：

定理一：设网络 G 的源为 S, 汇和 T，F
和 C 分别为 G 的流和容量，则 F 是最大流当且仅当 G 中不存在可增广路。

由此定理可以设计很多算法来计算最大流，Dinic 算法是其中一种比较高效的方法，其复杂度为 O(n2*m)

Dinic 算法的基本步骤为:

1) 计算残余网络的层次图。我们定义 h[i] 为顶点 i 距离源 S 所经过到最小边数，求出所有顶点的 h 值，h[] 值相同的顶点属于同一层，这就是网络的层次图。

2) 在层次图上进行 BFS 增广，直到不存在增广路径。这时求得的增广路径上顶点是分层的，路径上不可能存在两个顶点属于同一层，即 h[i]== h[j] (i!= j )。同时，求得层次图后，我们可以在层次图上进行多次增广。

3) 重复 1 和
2。直到不存在增广路径。

可知，Dinic 算法找到的增广路径是最短的，即经过的顶点数最少。再者，Dinic 算法找一条增广路径同时可以找到多条，类似增广路径树。比如我们找到了一条增广路径，这条增广路径所增加的流量为 C,则这条增广路径上必然有一条边<i,j>残余容量为 C，这是我们不必又从起点开始寻找增广路，而是从 i 顶点出发找增广路，这样就减少了重复计算，提高了效率，这好像就是所说的多路增广

/*
Pku 3469 Dual Core CPU ( Dinic )
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int const N= 20010, M= 880010;
int n, m, idx= -1, S, T;
 
#define min(a,b) ( (a)< (b)? (a): (b) )
 
struct Edge{
    int wt, v;

    Edge* next;
 }tb[M];

Edge* mat[N];
 int h[N], que[N];

void inline add( int u, int v, int x, int y ){

    idx++;

    tb[idx].wt= x; tb[idx].v= v;

    tb[idx].next= mat[u]; mat[u]= tb+ idx;

    idx++;

    tb[idx].wt= y; tb[idx].v= u;

    tb[idx].next= mat[v]; mat[v]= tb+ idx;
 }

inline Edge* reserve( Edge* p ){

    return tb+ ((p-tb)^1);
 }

int bfs(){

    int head= 0, tail= 0;

    for( int i= 0; i<= T; ++i ) h[i]= -1;

    que[0]= S; h[S]= 0;

    while( head<= tail ){

        int u= que[head++];

        for( Edge* p= mat[u]; p; p= p->next ){

            int v= p->v, w= p->wt;

            if( h[v]== -1 && w> 0 ){

                h[v]= h[u]+ 1; que[++tail]= v;

            }

        }

    }

    return h[T]!= -1;
 }

int dfs( int u, int flow ){

    if( u== T ) return flow;

    int tf= 0, f;

    for( Edge* p= mat[u]; p; p= p->next ){

        int v= p->v, w= p->wt;

        if( h[v]== h[u]+ 1 && w> 0 && tf< flow && ( f= dfs( v, min( w, flow- tf ) ) ) ){

            p->wt-= f;

            reserve(p)->wt+= f;

            tf+= f;

        }

    }

    if( tf== 0 ) h[u]= -1;

    return tf;
 }

int inline read(){

    char ch;

    int d;

    while( ch= getchar(), ch== ' ' || ch== 'n');

    d= ch- '0';

    while( ch= getchar(), ch>= '0' && ch<= '9' )

    d= d* 10+ ch- '0';

    return d;
 }

int main(){

    scanf("%d%d",&n,&m );

    S= 0, T= n+ 1; idx= -1;

    for( int i= 0; i<= n+ 1; ++i ) mat[i]= 0;

    for( int i= 1; i<= n; ++i ){

        int x, y;

        x= read(),y=read();

        add( S, i, x, 0 ); add( i, T, y, 0 );

    }

    for( int i= 0; i< m; ++i ){

        int x, y, z;

        x=read(),y=read(),z=read();

        add( x, y, z, z );

    }

    int ans= 0;

    while( bfs()) ans+= dfs( S, 0x7fffffff );

    printf("%dn", ans );

    return 0;
 }

然则算法的优化是无尽头的，Dinic 算法要多次计算层次图，增加了复杂度。是不是可以不多次计算层次图呢？答案是肯定，这就产生了 SAP 算法。

SAP 计算的是反向图的层次图，这和原图的层次图是作用是一样的，当然其实Dinic也可以计算反向图的层次图。确保增广路径最短，SAP 意思就是 Shortest Augmenting Paths，最短增广路径。计算反向图的层次图是便于重新给顶点标号，即重新确定其层次图。具体做法为，当我们找到一条经过顶点 i 的增广路径后，对于所有边<i,j>，计算出 m= min{ h[j] ]，这是我们就可以把 i 重新标号为 h[i]= min+ 1。实际上，我们可以首先不需要计算反向图的层次图，而是把所有顶点的层次标为0，这对效率没多大影响。然则这样优化后还不够，又出现了一个 gap 优化。所谓 gap 优化就是计算出层次图后，层次出现断层，这是可以确定残余网络中不存在增广路径了，算法就可以提前结束。这个优化看似微小，实际作用确不小。做法就是保存某一个标号在残余网络中出现的次数，如果是 0 ，就断层了。