Advertisement
LinKin

Min Cost Max Flow

Jun 25th, 2013
310
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. /*
  2.  * Algoritm : Min Cost Max Flow using Bellmen Ford
  3.  * Note : Vertex are 0 indexing Based
  4.  */
  5. #include<stdio.h>
  6. #include<string.h>
  7. #include<vector>
  8. #include<algorithm>
  9. using namespace std;
  10. #define MAX_V 3777
  11. #define INF 777777777
  12. struct NODE{
  13.     long v,Cap,Cost,RevInd;// This ind is necesery for multigraph to knw which edge is used to take flow
  14. };
  15. vector<NODE> Edge[ MAX_V+7];
  16. long nV,nE,P;
  17. long SRC,TNK;
  18. // This PInd is neceserry for multigraph to knw which edge ind of parent is used to take flow
  19. long Par[ MAX_V+7],PInd[MAX_V+7];
  20. long SD[MAX_V+7];// Shortest path
  21.  
  22. void SetEdge( long u,long v,long Cap,long Cost )
  23. {
  24.     NODE U ={ v,Cap,Cost,Edge[v].size()};
  25.     NODE V ={ u,0,-Cost,Edge[u].size()};
  26.     Edge[u].push_back( U);
  27.     Edge[v].push_back( V);
  28. }
  29.  
  30. bool BFord( void)
  31. {
  32.     long i,u,k;
  33.     for( i=0;i<nV;i++){
  34.         Par[i] =-1;SD[i] =INF;
  35.     }
  36.     bool IsChange =true;
  37.     SD[SRC] =0;
  38.     while( IsChange ){
  39.         IsChange =false;
  40.         for( u=SRC;u<=TNK;u++){
  41.             for( i=0;i<Edge[u].size();i++){
  42.                 if( !Edge[u][i].Cap) continue;
  43.                 long v = Edge[u][i].v;
  44.                 TD = SD[u] +Edge[u][i].Cost;
  45.                 // relaxation
  46.                 if( SD[v] > TD ){
  47.                     SD[v] = TD;Par[v] =u;PInd[v] =i;
  48.                     IsChange =true;
  49.                 }
  50.             }
  51.         }
  52.     }
  53.     return Par[TNK]!=-1;
  54. }
  55.  
  56. long FindVol( long s,long t)
  57. {
  58.     long Cap =Edge[ Par[t]][ PInd[t]].Cap;
  59.     if( s==Par[t]) return Cap;
  60.     else return min( Cap,FindVol( s,Par[t]));
  61. }
  62.  
  63. long AugmentPath( long s,long t,long V)
  64. {
  65.     if( s==t ) return 0;
  66.     long Cost =Edge[ Par[t]][PInd[t]].Cost*V;
  67.     Edge[ Par[t]][ PInd[t]].Cap -=V;
  68.     Edge[ t][ Edge[ Par[t]][PInd[t]].RevInd].Cap +=V;
  69.     return Cost + AugmentPath( s,Par[t],V);
  70. }
  71.  
  72. void MinCost( long &Flow,long &Cost)
  73. {
  74.     Flow = Cost = 0;
  75.     while( BFord()){
  76.         long V =FindVol( SRC,TNK );
  77.         Flow +=V;
  78.         Cost +=AugmentPath( SRC,TNK,V);
  79.     }
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement