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

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

实验目的：
1.理解迭代改进基本原理；
2.掌握最短增益路径法；

实验平台：
Microsoft Visual C++ 6.0

实验过程：
1.编程实现最短增益路径算法：
#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;
class G
{
public:
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 int[N+1];
Sign=new int[N+1];
P=new int[N+1];

for(int i=1;i<=N;i++)
{
Map[i]=new int[N+1];
Flow[i]=new int[N+1];
Rest[i]=new int[N+1];
Sign[i]=0;
P[i]=0;
}
for(i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
Map[i][j]=0;
Flow[i][j]=0;
Rest[i][j]=0;
}
}

int G::Min(int a,int b)
{
if(a<b) return a;
return b;
}

void G::Edge(int a,int b,int flow)
{
if(a<0 || a>N || b<0 || b>N) return;
Map[a][b]=flow;
}

void G::Update()
{
for(int i=1;i<=N;i++)
{
Sign[i]=0;
for(int j=1;j<=N;j++)
Rest[i][j]=Map[i][j]-Flow[i][j];
}
}

bool G::SignN()
{
Update();
queue<int> que;
que.push(Start);
Sign[Start]=1;
P[Start]=1000000;
Pre[Start]=-1;

while(!que.empty())
{
int head=que.front();
que.pop();
for(int i=1;i<=N;i++)
{
if(Rest[head][i]>0 && Sign[i]==0)
{
P[i]=Min(P[head],Rest[head][i]);
Pre[i]=head;
Sign[i]=1;
if(i==End) return true;
que.push(i);
}
}
for(i=1;i<=N;i++)
{
if(Flow[i][head]>0 && Sign[i]==0)
{
P[i]=Min(P[head],Flow[i][head]);
Pre[i]=-head;
Sign[i]=1;
if(i==End) return true;
que.push(i);
}
}
}
return false;
}

void G::Maxflow()
{
int maxflow=0;
while(SignN())
{
maxflow=maxflow+P[End];
for(int i=End;i>1;i=abs(Pre[i]))
{
if(Pre[i]>0)
Flow[Pre[i]][i]=Flow[Pre[i]][i]+P[End];
if(Pre[i]<0)
Flow[i][abs(Pre[i])]=Flow[i][abs(Pre[i])]-P[End];
}
}
cout<<"最大流:"<<maxflow<<endl;
}

void G::Leastcut()
{
cout<<"最小割:";
int leastcut=0;
for(int i=1;i<=N;i++)
{
if(Sign[i]==1)
for(int j=1;j<=N;j++)
if(Map[i][j]>0 && Map[i][j]==Flow[i][j] && Sign[j]==0)
{
cout<<"("<<i<<","<<j<<") ";
leastcut=leastcut+Map[i][j];
}
}
cout<<endl<<"最小割流量:"<<leastcut<<endl;
}

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)
最小割流量:10

b.测试代码：
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);
Graph.Edge(4, 6, 1);
Graph.Edge(5, 6, 5);
Graph.Maxflow();
Graph.Leastcut();
}
测试结果：
最大流:5
最小割:(1,2) (3,5) (4,6)
最小割流量:5

第7页