学步园

有了上一篇文章最大流的基础，理解最小费用最大流就很容易了，但是我还是想了挺久的。当我看到最小费用最大流问题这篇文章，才开始觉悟。于是做了如下实现。

/*
	每次找出最短路径（该路径的单位费用和最小）记录该路径（next数组）
	直到找不出这样一条路径(实际上是没有到达终点的路，因为图中的路是会不停的变动)。我们这里的是Distance[0]>=MAX

*/

#include<iostream>
using namespace std;
#define MAX 1024

int nodes,edges;//节点数和边数
int capacity[MAX][MAX];//节点之间的流量
int cost[MAX][MAX];//节点之间的单位费用

int minCost=0;//统计最小费用
int next[MAX];//为了记录最短路径

int Distance[MAX];//表示每个节点到终点的费用
inline int min(int a,int b)
{
	return a<b?a:b;
}
void resetThePath()//找出最短路径,这里还需优化。
{
	int i,j;
	for(i=0;i<nodes-1;i++)
		Distance[i]=MAX;
	Distance[nodes-1]=0;
	next[nodes-1]=-1;
	
	for(i=nodes-1;i>=0;i--)
	{
		for(j=0;j<nodes;j++)
		{
			if(cost[j][i]!=MAX)
			{
				if(Distance[j]>(Distance[i]+cost[j][i]))
				{
					Distance[j]=Distance[i]+cost[j][i];
					next[j]=i;
				}
			}
		}	
	}

	for(i=nodes-1;i>=0;i--)
	{
		for(j=0;j<nodes;j++)
		{
			if(cost[j][i]!=MAX)
			{
				if(Distance[j]>(Distance[i]+cost[j][i]))
				{
					Distance[j]=Distance[i]+cost[j][i];
					next[j]=i;
				}
		}	
	}	
}

void minCostMaxFlow()
{
	while(1)
	{
		int i;
		resetThePath();
		if(Distance[0]>=MAX)//没有最短路径
			break;
		int increase=MAX;//本次最短路径中的流量
		for(i=0;next[i]!=-1;i=next[i])
		{
			increase=min(increase,capacity[i][next[i]]);
		}
		for(i=0;next[i]!=-1;i=next[i])//改变图的路径信息
		{
			capacity[i][next[i]]-=increase;
			capacity[next[i]][i]+=increase;
			if(cost[next[i]][i]==MAX)
				cost[next[i]][i]=cost[i][next[i]]*(-1);
			if(!capacity[i][next[i]])
				cost[i][next[i]]=MAX;
		}
		minCost+=Distance[0]*increase;
	}		
}

void main()
{
	while(1)
	{
		cin>>nodes>>edges;
		int i,j;
		for(i=0;i<nodes;i++)
		{
			for(j=0;j<nodes;j++)
				capacity[i][j]=0;
			for(j=0;j<nodes;j++)
				cost[i][j]=MAX;
		}
		int firstnode,secondnode,capa,cos;
		for(i=0;i<edges;i++)
		{
			cin>>firstnode>>secondnode>>capa>>cos;
			capacity[firstnode][secondnode]=capa;
			cost[firstnode][secondnode]=cos;
		}
		minCostMaxFlow();
		cout<<minCost<<endl;
	}
}