“网络流博大精深”—sideman语
一个基本的网络流问题 点击打开链接 感谢WHD的大力支持
最早知道网络流的内容便是最大流问题,最大流问题很好理解:
解释一定要通俗!
如右图所示,有一个管道系统,节点{1,2,3,4},有向管道{A,B,C,D,E},即有向图一张. [1]是源点,有无限的水量,[4]是汇点,管道容量如图所示.试问[4]点最大可接收的水的流量?
这便是简单的最大流问题,显然[4]点的最大流量为50
死理性派请注意:流量是单位时间内的,总可以了吧!
然而对于复杂图的最大流方法是什么呢,有EK,Dinic,SAP,etc.下面介绍Dinic算法(看代码的直接点这)
引自NOCOW,相当简单是吧…
一般情况下在Dinic算法中,我们只记录某一边的剩余流量.
残量网络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量网络, 层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3}) DFS:这个就不用说了吧… 增广 :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差) 增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?) 剩余流量:当一条边被增广之后(即它是增广路的一部分,或者说增广路通过这条边),这条边还能通过的流量. 反向弧:我们在Dinic算法中,对于一条有向边,我们需要建立另一条反向边(弧),当正向(输入数据)边剩余流量减少I时,反向弧剩余流量增加I注意(可以无视):
Dinic(其实其他的好多)算法中寻找到增广路后要将反向边增加I Dinic中DFS时只在分层图中DFS,意思是说DFS的下一个节点的Dis(距源点的距离)要比自己的Dis大1,例如在图1中第一个次DFS中,1->2->4 这条路径是不合法的,因为Dis[2]=1;Dis[4]=1; 步骤2中“获得这条路径的流量I “实现:DFS函数有参量low,代表从源点到现在最窄的(剩余流量最小)的边的剩余流量,当DFS到汇点是,Low便是我们要的流量I这一段不理解也不是不可以,对于会写算法没什么帮助,如果你着急,直接无视即可. 先举一个例子(如右图):
必须使用反向弧的流网络在这幅图中我们首先要增广1->2->4->6,这时可以获得一个容量为2的流,但是如果不建立4->2反向弧的话,则无法进一步增广,最终答案为2,显然是不对的,然而如果建立了反向弧4->2,则第二次能进行1->3->4->2->5->6的增广,最大流为3.
Comzyh对反向弧的理解可以说是”偷梁换柱“,请仔细阅读:在上面的例子中,我们可以看出,最终结果是1->2->5->6和1->2->4->6和1->3->4->6.当增广完1->2->4->5(代号A)后,在增广1->3->4->2->5->6(代号B),相当于将经过节点2的A流从中截流1(总共是2)走2->5>6,而不走2->4>6了,同时B流也从节点4截流出1(总共是1)走4->6而不是4->2->5->6,相当于AB流做加法.
简单的说反向弧为今后提供反悔的机会,让前面不走这条路而走别的路.
Alwa同学非要我给他的文章加一个链接,大家可以看看他的文章: 有关网络流中的反向弧和增广路
最大流算法一直有一个入门经典题:POJ 1273 或者是UCACO 4_2_1 来自NOCOW(中文) 这两个是同一个题
给出这道题的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 /* Program:POJ 1273 / Dinic Author:Comzyh */ #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #define min(x,y) ((x<y)?(x):(y)) using namespace std ; const int MAX = 0x5fffffff ; // int tab [ 250 ] [ 250 ] ; //邻接矩阵 int dis [ 250 ] ; //距源点距离,分层图 int q [ 2000 ] , h , r ; //BFS队列 ,首,尾 int N , M , ANS ; //N:点数;M,边数 int BFS ( ) { int i , j ; memset ( dis , 0xff , sizeof ( dis ) ) ; //以-1填充 dis [ 1 ] = 0 ; h = 0 ; r = 1 ; q [ 1 ] = 1 ; while ( h < r ) { j = q [ ++ h ] ; for ( i = 1 ; i <= N ; i ++ ) if ( dis [ i ] < 0 && tab [ j ] [ i ] > 0 ) { dis [ i ] = dis [ j ] + 1 ; q [ ++ r ] = i ; } } if ( dis [ N ] > 0 ) return 1 ; else return 0 ; //汇点的DIS小于零,表明BFS不到汇点 } //Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广 int find ( int x , int low ) //Low是源点到现在最窄的(剩余流量最小)的边的剩余流量 { int i , a = 0 ; if ( x == N ) return low ; //是汇点 for ( i = 1 ; i <= N ; i ++ ) if ( tab [ x ] [ i ] > 0 //联通 && dis [ i ] == dis [ x ] + 1 //是分层图的下一层 && ( a = find ( i , min ( low , tab [ x ] [ i ] ) ) ) ) //能到汇点(a <> 0) { tab [ x ] [ i ] -= a ; tab [ i ] [ x ] += a ; return a ; } return 0 ; } int main ( ) { //freopen("ditch.in" ,"r",stdin ); //freopen("ditch.out","w",stdout); int i , j , f , t , flow , tans ; while ( scanf ( "%d%d" , &M , &N ) != EOF ) { memset ( tab , 0 , sizeof ( tab ) ) ; for ( i = 1 ; i <= M ; i ++ ) { scanf ( "%d%d%d" , &f , &t , &flow ) ; tab [ f ] [ t ] += flow ; } // ANS = 0 ; while ( BFS ( ) ) //要不停地建立分层图,如果BFS不到汇点才结束 { while ( tans = find ( 1 , 0x7fffffff ) ) ANS += tans ; //一次BFS要不停地找增广路,直到找不到为止 } printf ( "%d\n" , ANS ) ; } system ( "pause" ) ; }
另一道题目是 POJ 1459 使用邻接表,采用当前弧优化
C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std ; int N , NP , NC , M ; struct Edge { int u , v , cap ; Edge ( ) { } Edge ( int u , int v , int cap ) : u ( u ) , v ( v ) , cap ( cap ) { } } es [ 150 * 150 ] ; int R , S , T ; vector < int > tab [ 109 ] ; // 边集 int dis [ 109 ] ; int current [ 109 ] ; void addedge ( int u , int v , int cap ) { tab [ u ] . push_back ( R ) ; es [ R ++ ] = Edge ( u , v , cap ) ; // 正向边 tab [ v ] . push_back ( R ) ; es [ R ++ ] = Edge ( v , u , 0 ) ; // 反向边容量为0 // 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2 } int BFS ( ) { queue < int > q ; q . push ( S ) ; memset ( dis , 0x3f , sizeof ( dis ) ) ; dis [ S ] = 0 ; while ( ! q . empty ( ) ) { int h = q . front ( ) ; q . pop ( ) ; for ( int i = 0 ; i < tab [ h ] . size ( ) ; i ++ ) { Edge &e = es [ tab [ h ] [ i ] ] ; if ( e . cap > 0 && dis [ e . v ] == 0x3f3f3f3f ) { dis [ e . v ] = dis [ h ] + 1 ; q . push ( e . v ) ; } } } return dis [ T ] < 0x3f3f3f3f ; // 返回是否能够到达汇点 } int dinic ( int x , int maxflow ) { if ( x == T ) return maxflow ; // i = current[x] 当前弧优化 for ( int i = current [ x ] ; i < tab [ x ] . size ( ) ; i ++ ) { current [ x ] = i ; Edge &e = es [ tab [ x ] [ i ] ] ; if ( dis [ e . v ] == dis [ x ] + 1 && e . cap > 0 ) { int flow = dinic ( e . v , min ( maxflow , e . cap ) ) ; if ( flow ) { e . cap -= flow ; // 正向边流量降低 es [ tab [ x ] [ i ] ^ 1 ] . cap += flow ; // 反向边流量增加 return flow ; } } } return 0 ; // 找不到增广路 退出 } int DINIC ( ) { int ans = 0 ; while ( BFS ( ) ) // 建立分层图 { int flow ; memset ( current , 0 , sizeof ( current ) ) ; // BFS后应当清空当前弧数组 while ( flow = dinic ( S , 0x3f3f3f3f ) ) // 一次BFS可以进行多次增广 ans += flow ; } return ans ; } int main ( ) { while ( scanf ( "%d%d%d%d" , &N , &NP , &NC , &M ) != EOF ) { R = 0 ; S = N ; T = N + 1 ; for ( int i = 0 ; i <= T ; i ++ ) tab [ i ] . clear ( ) ; for ( int i = 0 ; i < M ; i ++ ) { int u , v , cap ; scanf ( " (%d,%d)%d" , &u , &v , &cap ) ; addedge ( u , v , cap ) ; } for ( int i = 0 ; i < NP ; i ++ ) { int u , p ; scanf ( " (%d)%d" , &u , &p ) ; addedge ( S , u , p ) ; } for ( int i = 0 ; i < NC ; i ++ ) { int u , c ; scanf ( " (%d)%d" , &u , &c ) ; addedge ( u , T , c ) ; } printf ( "%d\n" , DINIC ( ) ) ; } return 0 ; }