//?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]??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?	{
		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?		for?（int?j?=?i;?++j?			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?	{
		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