Advertisement
LinKin

Dinic's max flow

Nov 17th, 2011
426
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. /*
  2.     Algorithm: Dinic'c max flow
  3.                using Edge List
  4. */
  5.  
  6. #include<stdio.h>
  7. #include<string.h>
  8.  
  9. #define MAX_V
  10. #define MAX_E
  11. #define INF 7777777
  12.  
  13. struct EDGE{
  14.     long v,c;
  15. };
  16. long nV;
  17. long SRC,TNK;
  18. long eI;
  19. EDGE Edge[MAX_E+7]; // edge list
  20. long Next[MAX_E+7]; // next pointer of vertex v
  21. long Last[MAX_V+7]; // last index of adj edge of vertex v
  22. long Dist[MAX_V+7]; // level from src
  23. long Start[MAX_V+7];// temporary used for last
  24.  
  25. inline void SetEdge( long u,long v,long c )
  26. {
  27.     Edge[eI].v = v;
  28.     Edge[eI].c = c;
  29.     Next[eI] = Last[u];
  30.     Last[u] = eI++;
  31.     Edge[eI].v = u;
  32.     Edge[eI].c = 0;
  33.     Next[eI] = Last[v];
  34.     Last[v] = eI++;
  35. }
  36.  
  37. long Q[MAX_V+7];
  38. long Frnt,End;
  39.  
  40. bool Bfs( void )
  41. {
  42.     Frnt = End = 0;
  43.     Q[End++] = SRC;
  44.     long i;
  45.     for( i=0;i<nV;i++){
  46.         Dist[i] = INF;
  47.     }
  48.     Dist[SRC] = 0;
  49.     long u,v;
  50.     while( Frnt<End ){
  51.         u = Q[Frnt++];
  52.         for( i=Last[u];i!=-1;i=Next[i]){
  53.             v = Edge[i].v;
  54.             if( !Edge[i].c || Dist[v]<INF ) continue;
  55.             Dist[v] = Dist[u] + 1;
  56.             Q[End++] = v;
  57.         }
  58.     }
  59.     return Dist[TNK] < INF;;
  60. }
  61.  
  62. #define MIN( a,b ) a<b ? a:b
  63.  
  64. long AugmentPath( long u,long f )
  65. {
  66.     if( u==TNK ) return f;
  67.     long Tot = 0;
  68.     for( long &i = Start[u];i!=-1;i=Next[i] ){
  69.         long v = Edge[i].v;
  70.         if( !Edge[i].c ) continue;
  71.         if( Dist[v] != Dist[u]+1 ) continue;
  72.         long Tmp = AugmentPath( v,MIN( f,Edge[i].c ));
  73.         Edge[i].c -= Tmp;
  74.         Edge[i ^ 1].c += Tmp;
  75.         Tot += Tmp;
  76.         f -= Tmp;
  77.         if( !f ) break;
  78.     }
  79.     return Tot;
  80. }
  81.  
  82. long MaxFlow( void )
  83. {
  84.     long Flw = 0;
  85.     while( Bfs()){
  86.         memcpy( Start,Last,(nV)*sizeof(long));
  87.         Flw += AugmentPath( SRC,2*INF );       
  88.     }
  89.     return Flw;
  90. }
  91.  
  92. long main( void )
  93. {
  94.     //freopen("text1.txt","r",stdin );
  95.     SRC = 0;
  96.     TNK = N+E;
  97.     nV = TNK+1;
  98.     eI = 0;
  99.     memset( Last,-1,nV*sizeof(long));
  100.     MaxFlow()){
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement