有关网络流的一个算法：求一个网络中的最大流.rar_最大流_最大网络流_网络 最大流_网络最大流_网络流

有关网络流的一个算法：求一个网络中的最大流。 #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); }