mf.cpp

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

#ifndef _MAXIMUM_FLOW
#define _MAXIMUM_FLOW

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

namespace Maximum_Flow{
  static const int MAXN=1000;		// 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;
  static const double INFI=1e400;

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

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

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

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

  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;
  }

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

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

  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]=INFI;

      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;
  }

  double MaxFlow(int n,int s,int t,double &cost){
    int cur,tail,tl,i,j,u,v;
    double flow;
    memset(f,0,sizeof(f));
    flow=0;
    cost=0;

    do{
      memset(d,0,sizeof(d));
      for (i=1;i<=n;i++) value[i]=INFI;
      open[0]=s;
      d[s]=INF;
      value[s]=0;
      tail=0;

      while (tail>=0){
	memset(mk,0,sizeof(mk));
	memcpy(oldque,open,sizeof(open));

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

      if (value[t]==INFI) 
	return flow;

      flow+=d[t];
      cost+=d[t]*value[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;
  }

  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[i+1],ev[i],c[i],f[i]);
    printf("******************************\n");
  }

  void Debug_Print_Cost(){			// 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 with cost %lf and the flow %lf\n",ev[i+1],ev[i],c[i],w[i],f[i]);
    printf("******************************\n");
  }

  void Maximum_Flow_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;

    int i,j;
    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 Maximum_Flow_Cost_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 cost[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;

    int i,j;
    double c;
    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],cost[i-1][j-1]);
    MaxFlow(nNode,1,nNode,c);
    cout << "The total cost is " << c << endl;
  }

};

int main(){
  Maximum_Flow::Maximum_Flow_Test();
  Maximum_Flow::Debug_Print();
  Maximum_Flow::Maximum_Flow_Cost_Test();
  Maximum_Flow::Debug_Print_Cost();

  return 0;
}

#endif