最大流/最小割的push-relabel算法的代码实现

最大流/最小割的push-relabel算法的代码实现

// Push_Relabel.cpp : 定义控制台应用程序的入口点。
//

//The Push-Relabel Algorithm 最大流的压入与重标记算法
#include “stdafx.h“
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100;
bool isMark[N] = {false};
bool isCheck[N] = {false};
bool flag[N]; //顶点是否在队列 vlist 中
int c[N][N] //有向边的容量
e[N] //余流
f[N][N] //流
h[N] //高度
n; //顶点数
list vlist //待排除顶点
vNearArr[N]; //邻接表

void Push（int x int y）
{
	int df = min（e[x] c[x][y]- f[x][y]）;
	f[x][y] += df;
	f[y][x] = -f[x][y];
	e[x] -= df;
	e[y] += df;
}

void Relabel（int x）
{
	h[x] = n*2-1;
	for （list::iterator iter = vNearArr[x].begin（）; iter != vNearArr[x].end（）; ++iter）
		if （h[*iter] < h[x] && c[x][*iter] > f[x][*iter]）
			h[x] = h[*iter];
	++h[x];
}

void Discharge（int x）
{
	list::iterator iter = vNearArr[x].begin（）;
	while （e[x] > 0） //有余流
	{
		if （iter == vNearArr[x].end（））
		{
			Relabel（x）;
			iter = vNearArr[x].begin（）;
		}
		if （h[x] == h[*iter]+1 && c[x][*iter] > f[x][*iter]）
		{
			Push（x *iter）;
			if （e[*iter] > 0 && !flag[*iter]）
				vlist.push_back（*iter）;
		}
		++iter;
	}
}
void Check（int index）
{
	isCheck[index] = true;

	int i=0;
	while （i	{
		if（c[index][i]>0 && （c[index][i]-f[index][i]>0）） //有余流
			isMark[i] = true;
		i++;
	}
}
void FindMinCut（）//最小割存在于源s能够到达的所有点集合（包括s），即s能够通过余量到达该点
{
	isMark[0] = true; //s永久可达到

	int i=0;
	while （i	{
		if（isMark[i] && !isCheck[i]） {
			Check（i）;
			i = 0;
		}
		else i++;
	}	
}

int Push_Relabel（）
{
	vlist.clear（）;

	//初始化前置流
	h[0] = n; 
	e[0] = 0;
	memset（flag+1 0 n-2）; //1和n-1（即源和汇）不在 vlist 中
	flag[0] = true; 
	flag[n-1] = true; //防止源、汇进入 vlist

	for （int i = 1; i < n; ++i）
	{
		h[i] = 0;  //初始化各顶点高度为 h（i）=0
		f[0][i] = c[0][i];  //初始化源与其他与之相连的 边流量f（0i）=边容量c（0i）
		f[i][0] = -c[0][i]; //反向边容量
		e[0] -= c[0][i];    //初始化源的 点余量e（0）=-c（0i）
		e[i] = c[0][i];     //初始化其他 点余量e（i）=c（0i）

		if （c[0][i] > 0 && i != n-1）
		{
			vlist.push_back（i）; //待排除顶点，压入栈
			flag[i] = true;
		}
	}

	//构造邻接表，每个点i的列表vNearArr[i]中存储与点i在图上相邻的点
	for （int i = 0; i < n-1; ++i）
		for （int j = i; ++j < n; ）
			if （c[j][i] > 0 || c[i][j] > 0）
			{
				vNearArr[i].push_back（j）;
				vNearArr[j].push_back（i）;
			};

	//排除队列中的顶点
	while （!vlist.empty（））
	{
		int x = vlist.front（）;
		Discharge（x）;
		vlist.pop_front（）;
		flag[x] = false;
	}

	FindMinCut（）;
	return e[n-1];
}

int main（）
{
	int m;
	fstream fptr;
	fptr.open（“graph_data.txt“ios::in）;

	fptr>>m;
	fptr>>n;
	
	for （int i = 0; i < n; ++i）
	{
		memset（c 0 sizeof（c[0][0]）*n）;
		memset（f 0 sizeof（f[0][0]）*n）;
		vNearArr[i].clear（）;
	}

	int x y w;
	while （!fptr.eof（）） 
	{
		fptr>>x;
		fptr>>y;
		fptr>>c[x][y];
	}
	fptr.close（）;
		
	printf（“%d\n“ Push_Relabel（））; //计算从0（源）到 n-1（汇）的最大流
	
	for （int i=0; i	{
		if（isMark[i]） printf（“%d “ i）;
	}
	printf（“\n“）;
	system（“PAU

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3238  2012-10-17 19:46  Push_Relabel.cpp

     文件         66  2012-10-16 12:15  graph_data.txt

----------- ---------  ---------- -----  ----

                 3304                    2