本人做的网络单纯型类

knight · 发表于 2004-7-5 23:16:07

<

>/*
 Name: NetWorkSimplex.h
 Copyright: Knight-Studio
 Author: Ran NI
 Date: 05-07-04 15:19
 Description: The Declaration of the NetWorkSimplex Class
*/
<

>#include <vector>
#include <fstream>
#include <math.h>
#include <complex>
#ifndef _NETWORKSIMPLEX_H_
#define _NETWORKSIMPLEX_H_
<

>using namespace std;
class NetWorkSimplex
{
 public:
NetWorkSimplex(vector<double> aa,vector<double> bb,vector<vector<bool> > bbb,vector<vector<double> > cc,vector<vector<double> > uu,vector<vector<double> > ll):a(aa),b(bb),C(cc),U(uu),L(ll),B(bbb),Potential(aa.size()+bb.size()+2,0),DepthFirstSerchSeries(aa.size()+bb.size()+2,0),Pred(aa.size()+bb.size()+2,0),Depth(aa.size()+bb.size()+2,0),Thread(aa.size()+bb.size()+2,0),CostPotential(1)
{
 if(Cost.size()!=0)
 {
 Cost.clear();
 }
 if(Connect.size()!=0)
 {
 Connect.clear();
 }
 if(Bound.size()!=0)
 {
 Bound.clear();
 }
 if(Length.size()!=0)
 {
 Length.clear();
 }
 if(SpanningTree.size()!=0)
 {
 SpanningTree.clear();
 }
 if(x.size()!=0)
 {
 x.clear();
 }
 for(int i=0;i<(int)(a.size()+b.size()+2);++i)
 {
 vector<double> zz(a.size()+b.size()+2,0);
 vector<bool> c(a.size()+b.size()+2,false);
 Connect.push_back(c);
 Cost.push_back(zz);
 x.push_back(zz);
 Length.push_back(zz);
 Bound.push_back(zz);
 }
 for(int i=0;i<(int)B.size();++i)
 {
 for(int j=0;j<(int)B.size();++j)
 {
 if(B[j]==true)
 {
 Cost[i+1][j+a.size()+1]=C[j];
 Length[i+1][j+a.size()+1]=L[j];
 Bound[i+1][j+a.size()+1]=U[j];
 Connect[i+1][j+a.size()+1]=true;
 }
 }
 }
 for(int i=0;i<(int)a.size()+1;++i)
 {
 if(i>0)
 {
 Connect[0]=true;
 Bound[0]=a[i-1];
 }
 }
 for(int i=(int)Connect.size()-1;i>(int)Connect.size()-b.size()-2;--i)
 {
 if(i<(int)Connect.size()-1)
 {
 Connect[Connect.size()-1]=true;
 Bound[(int)Connect.size()-1]=b[(int)b.size()-((int)Connect.size()-i-1)];
 }
 }
 Change=0;
}
void InitialSpanningTree();
double LowestCost(int &c);
vector<int> FindLine(int s,int t);
int FindLeaf(vector<vector<bool> >);
void ComputeNodePotential();
complex<int> LeavingArc(complex<int>);
bool Judge(int ,int,bool);
void ComputeArcFlow();
complex<int> EnteringArc();
void DepthFirstSearch();
bool Judge(complex<int> c);
void ComputePotantial();
void Update(complex<int>,complex<int>);
vector<vector<double> > GetOptimalSolution()
{
 return Solution;
}

 protected:
vector<double> a;
vector<double> b;
vector<vector<bool> > B;
vector<vector<double> > C;
vector<vector<double> > U;
vector<vector<double> > L;
vector<vector<bool> > Connect;
vector<vector<double> > Cost;
vector<vector<double> > Bound;
vector<vector<double> > Length;
vector<vector<bool> > SpanningTree;
vector<double> Potential;
vector<vector<double> > x;
vector<vector<double> > Solution;
vector<int> DepthFirstSerchSeries;
vector<int> Pred;
vector<int> Depth;
vector<int> Thread;
vector<vector<double> > CostPotential;
int Change;
};
#endif

knight · 发表于 2004-7-5 23:18:10

<

>/*
 Name: NetWorkSimplex.cpp
 Copyright: Knight-Studio
 Author: Ran NI
 Date: 05-07-04 15:19
 Description: The Definition of the NetWorkSimplex Class
*/<

>#include <vector>
#include <iostream>
#include <complex>
#include <fstream>
#include <stack>
#include <algorithm>
#include <math.h>
#include "FordFulkerson.h"
#include "NetWorkSimplex.h"<

>using namespace std;void NetWorkSimplex::InitialSpanningTree()
{
 FordFulkerson initiall(Bound,Connect);
 vector<vector<double> > initial=initiall.Calculate();
 SpanningTree=Connect;
 x=initial;
 for(int i=0;i<(int)x.size();++i)
 for(int j=0;j<(int)x.size();++j)
 {
 if((x[j]>0)&&(x[j]<Bound[j])&&(Connect[j]==true))
 {
 SpanningTree[j]=true;
 SpanningTree[j]=true;
 }
 else if(((x[j]==0)||(x[j]==Bound[j]))&&(Connect[j]==true))
 {
 SpanningTree[j]=false;
 SpanningTree[j]=false;
 }
 }
 SpanningTree[0][1]=true;
 SpanningTree[1][0]=true;
 SpanningTree[SpanningTree.size()-1][SpanningTree.size()-2]=true;
 SpanningTree[SpanningTree.size()-2][SpanningTree.size()-1]=true;
 vector<int> close;
 close.push_back(0);
 bool tt=false;
 while(close.size()!=SpanningTree.size())
 {
 do
 {
 tt=false;
 int j=0;
 while((j<(int)close.size())&&(tt==false))
 {
 int i=0;
 while((i<(int)SpanningTree.size())&&(tt==false))
 {
 if((SpanningTree[close[j]]==true)&&((SpanningTree[close[j]]==true)))
 {
 if(find(close.begin(),close.end(),i)==close.end())
 {
 tt=true;
 close.push_back(i);
 }
 }
 ++i;
 }
 ++j;
 }
 }while(tt==true);
 int i=0;
 bool jud=false;
 while((i<(int)SpanningTree.size())&&(jud==false))
 {
 if(find(close.begin(),close.end(),i)==close.end())
 {
 int j=0;
 jud=false;
 while((!jud)&&(j<(int)close.size()))
 {
 if(((Connect[close[j]]==true)||(Connect[close[j]]==true))&&((SpanningTree[close[j]]==false)&&(SpanningTree[close[j]]==false)))
 {
 jud=true;
 SpanningTree[close[j]]=true;
 SpanningTree[close[j]]=true;
 close.push_back(i);
 }
 ++j;
 }
 }
 ++i;
 }
 }
}void NetWorkSimplex:epthFirstSearch()
{
 stack<int> ss;
 ss.push(0);
 vector<int> contain;
 contain.push_back(0);
 for(int i=0;i<(int)Pred.size();++i)
 {
 Pred=-1;
 }
 while(!ss.empty())
 {
 int i=ss.top();
 bool tag=false;
 int j=0;
 while((j<(int)SpanningTree.size())&&(tag==false))
 {
 if((SpanningTree[j]==true)||(SpanningTree[j]==true))
 {
 if(find(contain.begin(),contain.end(),j)==contain.end())
 {
 tag=true;
 ss.push(j);
 Pred[j]=i;
 contain.push_back(j);
 }
 }
 ++j;
 }
 if(tag==false)
 {
 ss.pop();
 }
 }
 for(int i=0;i<(int)contain.size();++i)
 {
 vector<int> :: iterator it=find(contain.begin(),contain.end(),i);
 if(it!=(contain.end()-1))
 {
 Thread=(*(it+1));
 }
 else
 {
 Thread[contain[contain.size()-1]]=contain[0];
 }
 }
 for(int i=0;i<(int)SpanningTree.size();++i)
 {
 int j=Pred;
 int nn=0;
 while(j!=-1)
 {
 j=Pred[j];
 ++nn;
 }
 Depth=nn;
 }
}void NetWorkSimplex::ComputeNodePotential()
{
 Potential[0]=0;
 int j=Thread[0];
 while(j!=0)
 {
 int i=Pred[j];
 if(Connect[j]==true)
 {
 Potential[j]=Potential-Cost[j];
 }
 else if(Connect[j]==true)
 {
 Potential[j]=Potential+Cost[j];
 }
 j=Thread[j];
 }
 CostPotential=Cost;
 for(int i=0;i<(int)Cost.size();++i)
 for(int j=0;j<(int)Cost.size();++j)
 {
 if(Connect[j]==true)
 {
 CostPotential[j]=Cost[j]-Potential+Potential[j];
 }
 }
}int NetWorkSimplex::FindLeaf(vector<vector<bool> > ss)
{
 bool tag=false;
 int i=ss.size()-1;
 while((tag==false)&&(i>=0))
 {
 int k=0;
 for(int j=0;j<(int)ss.size();++j)
 {
 if((ss[j]==true)||(ss[j]==true))
 {
 ++k;
 }
 }
 if(k==1)
 {
 tag=true;
 }
 else
 {
 tag=false;
 --i;
 }
 }
 if(i<0)
 {
 return -1;
 }
 else
 {
 return i;
 }
}complex<int> NetWorkSimplex::EnteringArc()
{
 vector<complex<int> > Candidate;
 for(int i=0;i<(int)Connect.size();++i)
 for(int j=0;j<(int)Connect.size();++j)
 {
 if((Connect[j]==true)&&(SpanningTree[j]==false))
 {
 if(x[j]==0)
 {
 if(CostPotential[j]<0)
 {
 complex<int> dd(i,j);
 Candidate.push_back(dd);
 }
 }else if(x[j]==Bound[j])
 {
 if(CostPotential[j]>0)
 {
 complex<int> dd(i,j);
 Candidate.push_back(dd);
 }
 }
 }
 }
 double temp=0;
 int kk(-1);
 if(Candidate.size()>0)
 {
 for(int i=0;i<(int)Candidate.size();++i)
 {
 if(fabs(CostPotential[Candidate.real()][Candidate.imag()])>temp)
 {
 kk=i;
 temp=fabs(CostPotential[Candidate.real()][Candidate.imag()]);
 }
 }
 return Candidate[kk];
 }
 else
 {
 complex<int> ff(-1,-1);
 return ff;
 }
}bool NetWorkSimplex::Judge(int s,int t,bool tag)
{
 bool result=false;
 if(tag==true)
 {
 if(Connect[t]==true)
 {
 if((x[t]==Bound[t]))
 {
 result=true;
 }
 }else if(Connect[t]==true)
 {
 if((x[t]==0))
 {
 result=true;
 }
 }
 }
 else
 {
 if(Connect[t]==true)
 {
 if((x[t]==0))
 {
 result=true;
 }
 }else if(Connect[t]==true)
 {
 if((x[t]==Bound[t]))
 {
 result=true;
 }
 }
 }
 return result;
}vector<int> NetWorkSimplex::FindLine(int s,int t)
{
 vector<int> contain1;
 contain1.push_back(s);
 vector<int> order(Connect.size(),-1);
 int num=1;
 do
 {
 for(int i=0;i<(int)contain1.size();++i)
 {
 for(int j=0;j<(int)Connect.size();++j)
 {
 if((SpanningTree[contain1][j]==true)&&(find(contain1.begin(),contain1.end(),j)==contain1.end()))
 {
 contain1.push_back(j);
 order[j]=contain1;
 }
 else if((SpanningTree[j][contain1]==true)&&(find(contain1.begin(),contain1.end(),j)==contain1.end()))
 {
 contain1.push_back(j);
 order[j]=contain1;
 }
 }
 }
 ++num;
 }while(num>Connect.size());
 vector<int> line;
 if(find(contain1.begin(),contain1.end(),t)==contain1.end())
 {
 return line;
 }
 else
 {
 line.push_back(t);
 int kk=t;
 while(order[kk]!=-1)
 {
 kk=order[kk];
 line.push_back(kk);
 }
 return line;
 }
}void NetWorkSimplex::ComputePotantial()
{
 for(int i=0;i<(int)Cost.size();++i)
 for(int j=0;j<(int)Cost.size();++j)
 {
 if(Connect[j]==true)
 {
 CostPotential[j]=Cost[j]-Potential+Potential[j];
 }
 }
}

knight · 发表于 2004-7-5 23:20:02

<

>complex<int> NetWorkSimplex:

eavingArc(complex<int> enter)
{
 int i=enter.real();
 int j=enter.imag();
 double delta=0;
 complex<int> result;
 if(x[j]<Bound[j])
 {
 delta=Bound[j]-x[j];
 }
 else
 {
 delta=x[j];
 }
 vector<complex<int> > con1;
 vector<complex<int> > con2;
 while(i!=j)
 {
 if(Depth>Depth[j])
 {
 int k=Pred;
 complex<int> dd(k,i);
 con1.push_back(dd);
 i=k;
 }
 else if(Depth<Depth[j])
 {
 int k=Pred[j];
 complex<int> dd(j,k);
 con2.push_back(dd);
 j=k;
 }
 else
 {
 int k=Pred;
 complex<int> dd(k,i);
 con1.push_back(dd);
 i=k;
 k=Pred[j];
 complex<int> ddd(j,k);
 con2.push_back(ddd);
 j=k;
 }
 }
 if(x[enter.real()][enter.imag()]<Bound[enter.real()][enter.imag()])
 {
 for(int ii=0;ii<(int)con1.size();++ii)
 {
 if(Connect[con1[ii].real()][con1[ii].imag()]==true)
 {
 if(delta>(Bound[con1[ii].real()][con1[ii].imag()]-x[con1[ii].real()][con1[ii].imag()]))
 {
 delta=(Bound[con1[ii].real()][con1[ii].imag()]-x[con1[ii].real()][con1[ii].imag()]);
 }
 }else if(Connect[con1[ii].imag()][con1[ii].real()]==true)
 {
 if(x[con1[ii].imag()][con1[ii].real()]<delta)
 {
 delta=x[con1[ii].imag()][con1[ii].real()];
 }
 }
 }
 for(int ii=0;ii<(int)con2.size();++ii)
 {
 if(Connect[con2[ii].real()][con2[ii].imag()]==true)
 {
 if(delta>(Bound[con2[ii].real()][con2[ii].imag()]-x[con2[ii].real()][con2[ii].imag()]))
 {
 delta=(Bound[con2[ii].real()][con2[ii].imag()]-x[con2[ii].real()][con2[ii].imag()]);
 }
 }else if(Connect[con2[ii].imag()][con2[ii].real()]==true)
 {
 if(x[con2[ii].imag()][con2[ii].real()]<delta)
 {
 delta=x[con2[ii].imag()][con2[ii].real()];
 }
 }
 }
 {
 for(int ii=0;ii<(int)con1.size();++ii)
 {
 if(Connect[con1[ii].real()][con1[ii].imag()]==true)
 {
 x[con1[ii].real()][con1[ii].imag()]+=delta;
 }
 else
 {
 x[con1[ii].imag()][con1[ii].real()]-=delta;
 }
 }
 for(int ii=0;ii<(int)con2.size();++ii)
 {
 if(Connect[con2[ii].real()][con2[ii].imag()]==true)
 {
 x[con2[ii].real()][con2[ii].imag()]+=delta;
 }
 else
 {
 x[con2[ii].imag()][con2[ii].real()]-=delta;
 }
 }
 x[enter.real()][enter.imag()]+=delta;
 int n=-1;
 int m=0;
 bool jg=false;
 for(int i=0;(i<(int)con1.size())&&(jg==false);++i)
 {
 if(Judge(con1.real(),con1.imag(),true))
 {
 jg=true;
 m=i;
 }
 }
 if(jg==true)
 {
 n=m;
 }
 int kn=-1;
 m=0;
 jg=false;
 for(int i=(int)con2.size()-1;(i>=0)&&(jg==false);--i)
 {
 if(Judge(con2.real(),con2.imag(),true))
 {
 jg=true;
 m=i;
 }
 }
 if(jg==true)
 {
 kn=m;
 }
 if(n!=-1)
 {
 if(kn>=0)
 {
 if(Connect[con2[kn].real()][con2[kn].imag()]==true)
 {
 result=con2[kn];
 }
 else
 {
 complex<int> dd(con2[kn].imag(),con2[kn].real());
 result=dd;
 }
 }
 else if(!Judge(enter.real(),enter.imag(),true))
 {
 if(Connect[con1[n].real()][con1[n].imag()]==true)
 {
 result=con1[n];
 }
 else
 {
 complex<int> dd(con1[n].imag(),con1[n].real());
 result=dd;
 }
 }
 else
 {
 result=enter;
 }
 }
 else if(n==-1)
 {
 if(kn>=0)
 {
 if(Connect[con2[kn].real()][con2[kn].imag()]==true)
 {
 result=con2[kn];
 }
 else
 {
 complex<int> dd(con2[kn].imag(),con2[kn].real());
 result=dd;
 }
 }
 else if(Judge(enter.real(),enter.imag(),true))
 {
 result=enter;
 }
 }
 SpanningTree[result.real()][result.imag()]=false;
 SpanningTree[result.imag()][result.real()]=false;
 }
 }

knight · 发表于 2004-7-5 23:20:32

else
 {
 for(int ii=0;ii<(int)con1.size();++ii)
 {
 if(Connect[con1[ii].imag()][con1[ii].real()]==true)
 {
 if(delta>(Bound[con1[ii].imag()][con1[ii].real()]-x[con1[ii].imag()][con1[ii].real()]))
 {
 delta=(Bound[con1[ii].imag()][con1[ii].real()]-x[con1[ii].imag()][con1[ii].real()]);
 }
 }else if(Connect[con1[ii].real()][con1[ii].imag()]==true)
 {
 if(x[con1[ii].real()][con1[ii].imag()]<delta)
 {
 delta=x[con1[ii].real()][con1[ii].imag()];
 }
 }
 }
 for(int ii=0;ii<(int)con2.size();++ii)
 {
 if(Connect[con2[ii].imag()][con2[ii].real()]==true)
 {
 if(delta>(Bound[con2[ii].imag()][con2[ii].real()]-x[con2[ii].imag()][con2[ii].real()]))
 {
 delta=(Bound[con2[ii].imag()][con2[ii].real()]-x[con2[ii].imag()][con2[ii].real()]);
 //cout<<delta<<"\t";
 }
 }else if(Connect[con2[ii].real()][con2[ii].imag()]==true)
 {
 if(x[con2[ii].real()][con2[ii].imag()]<delta)
 {
 delta=x[con2[ii].real()][con2[ii].imag()];
 //cout<<delta<<"\t";
 }
 }
 }
 {
 for(int ii=0;ii<(int)con1.size();++ii)
 {
 if(Connect[con1[ii].imag()][con1[ii].real()]==true)
 {
 x[con1[ii].imag()][con1[ii].real()]+=delta;
 }
 else
 {
 x[con1[ii].real()][con1[ii].imag()]-=delta;
 }
 }
 for(int ii=0;ii<(int)con2.size();++ii)
 {
 if(Connect[con2[ii].imag()][con2[ii].real()]==true)
 {
 x[con2[ii].imag()][con2[ii].real()]+=delta;
 }
 else
 {
 x[con2[ii].imag()][con2[ii].real()]-=delta;
 }
 }
 x[enter.real()][enter.imag()]-=delta;
 int n=-1;
 int m=0;
 bool jg=false;
 for(int i=0;(i<(int)con2.size())&&(jg==false);++i)
 {
 if(Judge(con2.real(),con2.imag(),false))
 {
 jg=true;
 m=i;
 }
 }
 if(jg==true)
 {
 n=m;
 }
 int kn=-1;
 m=0;
 jg=false;
 for(int i=(int)con1.size()-1;(i>=0)&&(jg==false);--i)
 {
 if(Judge(con1.real(),con1.imag(),false))
 {
 jg=true;
 m=i;
 }
 }
 if(jg==true)
 {
 kn=m;
 }
 if(n!=-1)
 {
 if(kn>=0)
 {
 if(Connect[con1[kn].real()][con1[kn].imag()]==true)
 {
 result=con1[kn];
 }
 else
 {
 complex<int> dd(con1[kn].imag(),con1[kn].real());
 result=dd;
 }
 }
 else if(!Judge(enter.real(),enter.imag(),false))
 {
 if(Connect[con2[n].real()][con2[n].imag()]==true)
 {
 result=con2[n];
 }
 else
 {
 complex<int> dd(con2[n].imag(),con2[n].real());
 result=dd;
 }
 }
 else
 {
 result=enter;
 }
 }
 else if(n==-1)
 {
 if(kn>=0)
 {
 if(Connect[con1[kn].real()][con1[kn].imag()]==true)
 {
 result=con1[kn];
 }
 else
 {
 complex<int> dd(con1[kn].imag(),con1[kn].real());
 result=dd;
 }
 }
 else if(Judge(enter.real(),enter.imag(),false))
 {
 result=enter;
 }
 }
 SpanningTree[result.real()][result.imag()]=false;
 SpanningTree[result.imag()][result.real()]=false;
 }
 }
 return result;
}

knight · 发表于 2004-7-5 23:20:58

<

>
void NetWorkSimplex::ComputeArcFlow()
{
 vector<double> bb(Connect.size(),0);
 for(int i=0;i<(int)a.size();++i)
 {
 bb[0]+=a;
 }
 bb[bb.size()-1]=-bb[0];
 for(int i=0;i<(int)Connect.size();++i)
 {
 for(int j=0;j<(int)Connect.size();++j)
 {
 if((Connect[j]==true)&&(SpanningTree[j]==false))
 {
 if(x[j]==Bound[j])
 {
 bb-=Bound[j];
 bb[j]+=Bound[j];
 }
 }
 }
 }
 vector<vector<bool> > sp(SpanningTree);
 int n=(int)sp.size();
 while(n>1)
 {
 int j=FindLeaf(sp);
 int i=Pred[j];
 if((Connect[j]==true))
 {
 x[j]=0-bb[j];
 }
 else
 {
 x[j]=bb[j];
 }
 bb+=bb[j];
 sp[j]=false;
 sp[j]=false;
 --n;
 }
}<>
void NetWorkSimplex::Update(complex<int> enter,complex<int> left)
{
 int y;
 vector<int> line(this->FindLine(0,left.imag()));
 if(line.size()==0)
 {
 y=left.imag();
 }
 else
 {
 y=left.real();
 }
 double change;
 line=this->FindLine(0,enter.real());
 if(line.size()!=0)
 {
 change=-(CostPotential[enter.real()][enter.imag()]);
 }
 else
 {
 change=CostPotential[enter.real()][enter.imag()];
 }
 Potential[y]+=change;
 int z=Thread[y];
 while(Depth[z]>Depth[y])
 {
 Potential[z]+=change;
 z=Thread[z];
 }
 SpanningTree[enter.real()][enter.imag()]=true;
 SpanningTree[enter.imag()][enter.real()]=true;
}<>bool NetWorkSimplex::Judge(complex<int> c)
{
 bool f=true;
 if((c.real()==(-1))&&(c.imag()==(-1)))
 {
 f=false;
 }
 return f;
}double NetWorkSimplex:owestCost(int &c)
{
 this->InitialSpanningTree();
 this->DepthFirstSearch();
 this->ComputeNodePotential();
 complex<int> enter=this->EnteringArc();
 double tem=0;
 for(int i=0;i<(int)x.size();++i)
 {
 for(int j=0;j<(int)x.size();++j)
 {
 tem+=x[j]*Cost[j];
 }
 }
 Change=0;
 while(Judge(enter))
 {
 complex<int> left=LeavingArc(enter);
 cout<<"EnterArc is\t"<<enter.real()<<"\t"<<enter.imag()<<endl;
 cout<<"LeavingArc is\t"<<left.real()<<"\t"<<left.imag()<<endl<<endl;
 Update(enter,left);
 ++Change;
 ComputePotantial();
 this->DepthFirstSearch();
 //ComputeArcFlow();
 enter=this->EnteringArc();
 }
 c=Change;
 double result(0);
 for(int i=0;i<(int)x.size();++i)
 for(int j=0;j<(int)x.size();++j)
 {
 result+=x[j]*Cost[j];
 }
 Solution.clear();
 for(int i=0;i<(int)a.size();++i)
 {
 vector<double> ss(b.size(),0);
 Solution.push_back(ss);
 }
 for(int i=0;i<(int)a.size();++i)
 {
 for(int j=0;j<(int)b.size();++j)
 {
 Solution[j]=x[i+1][1+a.size()+j];
 }
 }
 return result;
}

knight · 发表于 2004-7-5 23:21:28

<

>/*
 Name: FordFulkerson.h
 Copyright: Knight-Studio
 Author: Ran NI
 Date: 05-07-04 15:20
 Description: The Declaration of the FordFulkerson Class
*/<

>#include <vector>
#include <complex>
#ifndef _FORDFULKERSON_H_
#define _FORDFULKERSON_H_<

>using namespace std;class FordFulkerson
{
 public:
FordFulkerson(vector<vector<double> > d,vector<vector<bool> > b):data(d),B(b)
{
 X.clear();
 for(int i=0;i<(int)data.size();++i)
 {
 vector<double> z(data.size(),0);
 X.push_back(z);
 }
}
vector<vector<double> > Calculate();
vector<int> FindLine();
void Augment(vector<int>);

 protected:
vector<vector<double> > data;
vector<vector<bool> > B;
vector<vector<double> > X;
};
#endif

knight · 发表于 2004-7-5 23:22:03

<

>/*
 Name: FordFulkerson.cpp
 Copyright: Knight-Studio
 Author: Ran NI
 Date: 05-07-04 15:20
 Description: The Definition of the FordFulkerson Class
*/<

>#include <vector>
#include <iostream>
#include <complex>
#include <algorithm>
#include <math.h>
#include "FordFulkerson.h"<

>using namespace std;void FordFulkerson::Augment(vector<int> line)
{
 double delta;
 if(B[line[1]][line[0]]==true)
 {
 delta=data[line[1]][line[0]]-X[line[1]][line[0]];
 }else if(B[line[0]][line[1]]==true)
 {
 delta=X[line[0]][line[1]];
 }
 for(int i=0;i<(int)line.size()-1;++i)
 {
 if(B[line[i+1]][line]==true)
 {
 double dd=data[line[i+1]][line]-X[line[i+1]][line];
 if(dd<delta)
 {
 delta=dd;
 }
 }
 else if(B[line][line[i+1]]==true)
 {
 double dd=X[line][line[i+1]];
 if(dd<delta)
 {
 delta=dd;
 }
 }
 }
 for(int i=0;i<(int)line.size()-1;++i)
 {
 if(B[line[i+1]][line]==true)
 {
 X[line[i+1]][line]+=delta;
 }
 else if(B[line][line[i+1]]==true)
 {
 X[line][line[i+1]]-=delta;
 }
 }
}vector<int> FordFulkerson::FindLine()
{
 vector<int> contain1;
 contain1.push_back(0);
 vector<int> contain11;
 vector<int> order(data.size(),-1);
 do
 {
 contain11=contain1;
 for(int i=0;i<(int)contain1.size();++i)
 {
 for(int j=0;j<(int)data.size();++j)
 {
 if((B[contain1][j]==true)&&(find(contain1.begin(),contain1.end(),j)==contain1.end()))
 {
 if(X[contain1][j]<data[contain1][j])
 {
 contain1.push_back(j);
 order[j]=contain1;
 }
 }
 else if((B[j][contain1]==true)&&(find(contain1.begin(),contain1.end(),j)==contain1.end()))
 {
 if(X[j][contain1]>0)
 {
 contain1.push_back(j);
 order[j]=contain1;
 }
 }
 }
 }
 }while(contain11.size()!=contain1.size());
 vector<int> line;
 if(find(contain1.begin(),contain1.end(),data.size()-1)==contain1.end())
 {
 return line;
 }
 else
 {
 line.push_back(data.size()-1);
 int kk=data.size()-1;
 while(order[kk]!=-1)
 {
 kk=order[kk];
 line.push_back(kk);
 }
 return line;
 }
}vector<vector<double> > FordFulkerson::Calculate()
{
 vector<int> line=this->FindLine();
 while(line.size()!=0)
 {
 this->Augment(line);
 line=this->FindLine();
 }
 return X;
}

anndyb · 发表于 2004-8-4 03:24:44

<

>版主：你好<

>这些程序都是同一页的吗？

knight · 发表于 2004-8-4 09:36:08

不是,根据注释头上的文件名,是多个文件,需放在同一个工程里,用比较新的编译器(比如Vc.net2003或者C++Builder6等支持新规范的编译器)。我是按顺序贴的，只要按这个顺序把程序放在相应的文件里就可以了。

		自动登录	找回密码
密码			注-册-帐-号