最大流-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 ,就断层了。

本文链接:最大流-Dinic算法和SAP算法简介

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:Rexdf,谢谢!^^


This entry was posted in ACM and tagged , , , . Bookmark the permalink.

3 Responses to 最大流-Dinic算法和SAP算法简介

Leave a Reply

Your email address will not be published.

*

:zsmilebig: :zsadbig: :zwiredbig: :zgreenhappy: more »

This site uses Akismet to reduce spam. Learn how your comment data is processed.