求一个网络中的最大流.txt

其中一部分是自己写得,一部分是摘录的,希望站长能批准,我以后一定多多努力上传!

有关网络流的一个算法：求一个网络中的最大流。

#include <iostream.h>

#define FALSE 0
#define TRUE 1

#define N 6
#define MAXSTREAM 999

int GraphMatrix[N][N]={{0,1,1,0,0,0},
         {0,0,1,1,1,0},
         {0,0,0,1,1,0},
         {0,0,0,0,1,1},
         {0,0,0,0,0,1},
         {0,0,0,0,0,0}};

int cStreamMatrix[N][N]={{0,3,7,0,0,0},
         {3,0,2,5,4,0},
         {7,2,0,1,4,0},
         {0,5,1,0,2,8},
         {0,4,4,2,0,3},
         {0,0,0,8,3,0}};

int fStreamMatrix[N][N]={{0,0,0,0,0,0},
         {0,0,0,0,0,0},
         {0,0,0,0,0,0},
         {0,0,0,0,0,0},
         {0,0,0,0,0,0},
         {0,0,0,0,0,0}};

struct NetNodeType
{ int Flag;
 int cStream;
 int fStream;
}NetMatrix[N+1][N+1];

struct NodeType
{ int Label;
 int Stream;
}Node[N+1];

void Initialize(void)
{  int i,j;

 for (i=1;i<=N;i++)
 { for (j=1;j<=N;j++)
  { NetMatrix[i][j].Flag=GraphMatrix[i-1][j-1];
   NetMatrix[i][j].cStream=cStreamMatrix[i-1][j-1];
   NetMatrix[i][j].fStream=fStreamMatrix[i-1][j-1];
  }
  Node[i].Label=Node[i].Stream=0;
 }
}

int Find_Maximum_Stream(void)
{ int z;
 int c,f,x,y,i,u,v;
 int Max_Stream_Found,dStream;

 dStream=MAXSTREAM;

 Node[1].Label=1; Node[1].Stream=MAXSTREAM;
 for (x=1;x<=N;x++)
  if (Node[x].Label!=0)
   for (y=1;y<=N;y++)
    if (NetMatrix[x][y].Flag==1 && Node[y].Label==0)
    { c=NetMatrix[x][y].cStream;
     f=NetMatrix[x][y].fStream;
     if (f<c)
     { Node[y].Label=x;
      Node[y].Stream=(((c-f)<Node[x].Stream)?(c-f):Node[x].Stream);
      if (Node[y].Stream<=dStream) dStream=Node[y].Stream;
     }
    }
    else if (NetMatrix[y][x].Flag==1 && Node[y].Label==0)
    { f=NetMatrix[y][x].fStream;
     if (f>0)
     { Node[y].Label=-x;
      Node[y].Stream=((f<Node[x].Stream)?f:Node[x].Stream);
      if (Node[y].Stream<=dStream) dStream=Node[y].Stream;
     }
    }

 if (Node[N].Label!=0)
 { u=N;
  do
  {  v=Node[u].Label;
   if (v>0)
    NetMatrix[v][u].fStream=NetMatrix[v][u].fStream+dStream;
   else if (v<0)
   {  v=-v;
    NetMatrix[u][v].fStream=NetMatrix[u][v].fStream-dStream;
   }
   u=v;
  }while (v!=1);
  for (i=1;i<=N+1;i++)
  { Node[i].Label=0;
   Node[i].Stream=0;
  }
  Max_Stream_Found=FALSE;
 }
 else
  Max_Stream_Found=TRUE;

 z=Max_Stream_Found;

 return(z);
}

void Output_Stream(void)
{ int MaxStream=0;
 int i,j;

 for (i=1;i<=N;i++)
  if (NetMatrix[1][i].Flag==1) MaxStream+=NetMatrix[1][i].fStream;

 cout<<"Maximum Stream="<<MaxStream<<endl;

 for (i=1;i<=N;i++)
 { for (j=1;j<=N;j++) cout<<NetMatrix[i][j].fStream<<' ';
  cout<<endl;
 }
}

int main(void)
{  int Found=FALSE;

 Initialize();

 do
 { Found=Find_Maximum_Stream();
 }while (Found==FALSE);

 Output_Stream();

 return(0);
}