cmincostflow.h

一个基于启发式算法的搬运工求解程序

/*
	1:double CMinCostFlow::Run(double *cap, double *pri, double *value, int source, int sink, int n, int maxflow = INF);
	2:参数说明
		cap:	二维数组的第一行的地址，边容量矩阵
		pri:	二维数组的第一行的地址，代价矩阵
		value:　二维数组的第一行的地址, 实际容量矩阵
		source:	源点
		sink:	汇点
		n:		cap的大小，n * n
		maxflow:求指定最大流的最小费用
		流图是一个有向图!
	3:参数只能传二维矩阵首地址或者用一维指针表示的矩阵。不能传二维指针!

*/

#pragma once
#include "CDijkstra.h"
#include <iostream>
using namespace std;

const int INF = 2000000000;

class CMinCostFlow
{
public:
	CMinCostFlow(): rprice(NULL), rcap(NULL) {}
	~CMinCostFlow()
	{
		delete []rprice;
		delete []rcap;
	}
	double Run(double *cap, double *pri, double *value, int source, int sink, int n, int maxflow = INF);
	
	double &Ref(double *p, int r, int c);
	int &Ref(int *p, int r, int c);
	void Show(double *p, char *inf);
private:
	double *cap;										//最大容量,指向二维数组参数第一行地址
	double *value;										//当前边值,
	double *price;										//代价
	double *rprice;										//残余代价
	double *rcap;										//残余容量
	double maxflow;										//最大流
	double nowflow;					
	int n;
	
	void MakeResidual();
	void SetValue(double *s, double value);				//适用于二维数组的连续空间
};

void CMinCostFlow::Show(double *p, char *inf)
{
	cout << inf << endl;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
			cout << i << '\t' << j << '\t' << Ref(p, i, j) << endl;
	}
	cout << endl;
}

double &CMinCostFlow::Ref (double *p, int r, int c)
{ 
	return *(p + r * n + c);
}

int &CMinCostFlow::Ref(int *p, int r, int c)
{
	return *(p + r * n + c);
}

double CMinCostFlow::Run(double *cap, double *pri, double *value, int source, int sink, int n, int maxflow)
{
	double flow;
	static double *dis = NULL;
	static int *path = NULL;
	static int *pathn = NULL;
	int i;
	int j;
	int v1;
	int v2;
	double r = 0;

	if(rprice == NULL || n != this->n)
	{
		dis = new double[n];
		pathn = new int[n];
		path = new int [n * n];
		rprice = new double [n * n];
		rcap = new double [n * n];
	}

	this->cap = cap;
	this->value = value;
	this->price = pri;
	this->maxflow = maxflow;	
	this->n = n;
	this->nowflow = 0;
	this->SetValue(value, 0);

	for(;;)
	{
		MakeResidual();			
		//Show(rcap, "rcap");
		CDijikstra::Run(rprice, n, source, dis, path, pathn, INF); 
		if(pathn[sink] == 0)
			break;
		flow = INF;
		for(i =1; i < pathn[sink]; i++)
		{
			v1 = Ref(path, sink, i - 1);
			v2 = Ref(path, sink, i);
			flow = flow > Ref(rcap, v1, v2) ? Ref(rcap, v1, v2) : flow;
		}
		if(maxflow != INF)
			flow = flow < maxflow - nowflow ? flow : maxflow - nowflow;
		for(i = 1; i < pathn[sink]; i++)
		{
			v1 = Ref(path, sink, i - 1);
			v2 = Ref(path, sink, i);
			if(Ref(rprice, v1, v2) >= 0)	// 顺向边
				Ref(value, v1, v2) += flow;
			else
				Ref(value, v2, v1) -= flow;
		}
		//Show(value, "value");
		nowflow += flow;
		if(nowflow == maxflow)
			break;
	}

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			r += Ref(value, i, j) * Ref(pri, i, j);
	return r;
}

void CMinCostFlow::SetValue(double *s, double value)
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			Ref(s, i, j) = value;
}

void CMinCostFlow::MakeResidual()
{
	int i;
	int j;

	SetValue(rprice, INF);
	SetValue(rcap, INF);
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			if(Ref(cap, i, j) != INF)	// 不应当存在平行边
			{
				//同向边	
				Ref(rcap, i, j) = Ref(value, i, j) == Ref(cap, i, j) ? INF : (Ref(cap, i, j) - Ref(value, i, j));
				Ref(rprice, i, j) = Ref(value, i, j) == Ref(cap, i, j) ? INF : Ref(price, i, j);

				//逆向边
				Ref(rcap, j, i) = Ref(value, i, j) == 0 ? INF : Ref(value, i, j);
				Ref(rprice, j, i) = Ref(value, i, j) == 0 ? INF : -Ref(price, i, j);
			}
}