mf.cpp~

最大最小流程序。包括最大流网络

#ifndef _MAXIMUM_FLOW
#define _MAXIMUM_FLOW

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <algorithm>
using namespace std;

class Maximum_Flow{
private:
  static const int MAXN=10;		// MAXN is the maxmum of the node
  static const int MAXM=2*MAXN*MAXN;	// MAXM is the maxmum of the edge
  static const int INF=0x3FFFFFFF;

  // The node in the graph must be marked 1..n

  double c[MAXM],f[MAXM];
  int ev[MAXM],be[MAXM],next[MAXM];
  double d[MAXN];
  int nbs[MAXN],pnt[MAXN],open[MAXN],mk[MAXN];
  int num;

  void Initialize(){
    memset(c,0,sizeof(c));
    memset(f,0,sizeof(f));
    memset(ev,0,sizeof(ev));
    memset(be,0,sizeof(be));
    memset(next,0,sizeof(next));
    num=0;

    memset(nbs,0,sizeof(nbs));
    memset(pnt,0,sizeof(pnt));
    memset(open,0,sizeof(open));
    memset(d,0,sizeof(d));
    memset(mk,0,sizeof(mk));
  }

  void AddEdge(int u,int v,int cc){
    next[++num]=nbs[u];
    nbs[u]=num;
    be[num]=num+1;
    ev[num]=v;
    c[num]=cc;
    f[num]=0;

    next[++num]=nbs[v];
    nbs[v]=num;
    be[num]=num-1;
    ev[num]=u;
    c[num]=0;
    f[num]=0;
  }

  double MaxFlow(int n,int s,int t){
    int cur,tail,i,j,u,v;
    double flow=0;
    do{
      memset(mk,0,sizeof(mk));
      memset(d,0,sizeof(d));
      open[0]=s;
      mk[s]=1;
      d[s]=INF;

      for (pnt[s]=cur=tail=0;cur<=tail && !mk[t];cur++){
	for (u=open[cur],j=nbs[u];j;j=next[j]){
	  v=ev[j];
	  if (!mk[v] && f[j]<c[j]){
	    mk[v]=1;
	    open[++tail]=v;
	    pnt[v]=j;
	    if (d[u]<c[j]-f[j]) 
	      d[v]=d[u];
	    else d[v]=c[j]-f[j];
	  }
	}
      }

      if (!mk[t])
	break;

      flow+=d[t];
      for (u=t;u!=s;u=ev[be[j]]){
	j=pnt[u];
	f[j]+=d[t];
	f[be[j]]=-f[j];
      }

    } while (d[t]>0);
    return flow;
  }

public:
  Maximum_Flow(){
    Initialize();
  }

  Maximum_Flow(int test){ // For test
    Initialize();

    int edge[6][6]={0,3,0,3,0,0,
		    0,0,3,2,0,0,
		    0,0,0,0,4,2,
		    0,0,0,0,2,0,
		    0,0,0,0,0,3,
		    0,0,0,0,0,0};
    int nNode=6;


    cout << "ok!\n";

    int i,j,k;
    for (i=1;i<=nNode;i++)
      for (j=1;j<=nNode;j++)
	if (edge[i-1][j-1])
	  AddEdge(i,j,edge[i-1][j-1]);
 //   MaxFlow(nNode,1,nNode);
  }

  void debug_print(){			// For test
    printf("****************************** There are the graph:\n");
    int i;
    for (i=1;i<=num;i+=2)
      printf("The edge < %d , %d > has the capcity %lf and the flow %lf\n",ev[num+1],ev[num],c[num],f[num]);
    printf("******************************\n");
  }

};

int main(){
  cout << "!!!!!!!!\n" ;
  Maximum_Flow mf(1);
  //  mf.debug_print();
  return 0;
}

#endif