最大流和最小割的最短增益路径法.doc

最大流和最小割的最短增益路径法最大流和最小割的最短增益路径法实验目的：1.理解迭代改进基本原理；2.掌握最短增益路径法；实验平台：Microsoft Visual C+ 6.0实验过程：1.编程实现最短增益路径算法：#include #include #include using namespace std;class Gpublic:G();G(int n,int start,int end);void Edge(int a,int b,int flow); /a,b之间的流量void Maxflow(); /计算最大流void Leastcut(); /计算最小割private:int N,Start,End, /N是顶点个数,Start是源点End是汇点*Map, /网络流量*Flow, /通过流量*Rest, /剩余流量*Pre, /标记流向,正为前向,负为后向*Sign, /顶点是否标记,0为未标记,1为已标记*P; /过程变量,记录流量bool SignN(); /标记顶点int Min(int a,int b); /计算最小值void Update(); /更新网络;G:G() Pre=NULL;G:G(int n,int start,int end)N=n;Start=start;End=end;Map=new int*N+1;Flow=new int*N+1;Rest=new int*N+1;Pre=new intN+1;Sign=new intN+1;P=new intN+1;for(int i=1;i=N;i+)Mapi=new intN+1;Flowi=new intN+1;Resti=new intN+1;Signi=0;Pi=0;for(i=1;i=N;i+)for(int j=1;j=N;j+)Mapij=0;Flowij=0;Restij=0;int G:Min(int a,int b)if(ab) return a;return b;void G:Edge(int a,int b,int flow)if(aN | bN) return;Mapab=flow;void G:Update()for(int i=1;i=N;i+)Signi=0;for(int j=1;j=N;j+)Restij=Mapij-Flowij;bool G:SignN()Update();queue que;que.push(Start);SignStart=1;PStart=1000000;PreStart=-1;while(!que.empty()int head=que.front();que.pop();for(int i=1;i0 & Signi=0)Pi=Min(Phead,Restheadi);Prei=head;Signi=1;if(i=End) return true;que.push(i);for(i=1;i0 & Signi=0)Pi=Min(Phead,Flowihead);Prei=-head;Signi=1;if(i=End) return true;que.push(i); return false;void G:Maxflow()int maxflow=0;while(SignN()maxflow=maxflow+PEnd;for(int i=End;i1;i=abs(Prei)if(Prei0)FlowPreii=FlowPreii+PEnd;if(Prei0)Flowiabs(Prei)=Flowiabs(Prei)-PEnd;cout最大流:maxflowendl;void G:Leastcut()cout最小割:;int leastcut=0;for(int i=1;i=N;i+)if(Signi=1)for(int j=1;j0 & Mapij=Flowij & Signj=0)cout(i,j) ;leastcut=leastcut+Mapij;coutendl最小割流量:leastcutendl;2.通过上述程序求解教材274页第二题：a.测试代码：void main()G Graph(6,1,6);Graph.Edge(1, 2, 5); Graph.Edge(1, 3, 6); Graph.Edge(2, 4, 4); Graph.Edge(2, 5, 2); Graph.Edge(3, 4, 7); Graph.Edge(4, 6, 8); Graph.Edge(5, 6, 4);Graph.Maxflow();Graph.Leastcut();测试结果：最大流:10最小割:(2,5) (4,6)最小割流量:10b.测试代码：void main()G Graph(6,1,6);Graph.Edge(1, 2, 2); Graph.Edge(1, 3, 7); Graph.Edge(2, 4, 3); Graph.Edge(2, 5, 4); Graph.Edge(3, 4, 4); Graph.Edge(3, 5, 2); Gr