Libre 6013 「网络流 24 题」负载平衡 （网络流，最小费用最大流）

Description

G 公司有n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

«编程任务：

对于给定的n 个环形排列的仓库的库存量，编程计算使n 个仓库的库存数量相同的最少搬运量。

Input

第1 行中有1 个正整数n（n<=100），表示有n个仓库。

第2 行中有n个正整数，表示n个仓库的库存量。

Output

将计算出的最少搬运量输出

Sample Input

5

17 9 14 16 4

Sample Output

11

Http

Libre:https://loj.ac/problem/6013

Source

网络流，最小费用最大流

解决思路

对于每一个仓库，我们从源点连出一条容量为仓库存储的货物数量费用为0的边，连到汇点连一条容量库存数目总和/n花费为0的边。在对于每一个相邻的仓库连容量为无穷大费用为1的边。这样跑一边最小费用最大流就可以得到最终的答案

代码

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxN=250;

const int maxM=maxN*maxN*4;

const int inf=2147483647;

class Edge

{

public:

	int u,v,cost,flow;

};

int n;

int cnt=-1;

int Head[maxN];

int Next[maxM];

Edge E[maxM];

int Dist[maxN];

int Flow[maxN];

int Path[maxN];

bool inqueue[maxN];

int Q[maxM];

void Add_Edge(int u,int v,int cost,int flow);

bool spfa();

int main()

{

	memset(Head,-1,sizeof(Head));

	int sum=0;

	scanf("%d",&n);

	for (int i=1;i<=n;i++)

	{

		int num;

		scanf("%d",&num);

		sum+=num;//求和，因为要统计所有仓库库存之和

		Add_Edge(0,i,0,num);//连接源点与仓库i

		if (i==1)//连接i与其前一个仓库，注意判断1的情况

			Add_Edge(1,n,1,inf);

		else

			Add_Edge(i,i-1,1,inf);

		if (i==n)//连接i与后一个仓库，注意判断n的情况

			Add_Edge(n,1,1,inf);

		else

			Add_Edge(i,i+1,1,inf);

	}

	sum=sum/n;

	for (int i=1;i<=n;i++)//连接i与汇点

		Add_Edge(i,n+1,0,sum);

	int Ans=0;//最小费用最大流

	while (spfa())

	{

		int now=n+1;

		int last=Path[now];

		while (now!=0)

		{

			E[last].flow-=Flow[n+1];

			E[last^1].flow+=Flow[n+1];

			now=E[last].u;

			last=Path[now];

		}

		Ans+=Dist[n+1]*Flow[n+1];

	}

	cout<<Ans<<endl;

	return 0;

}

void Add_Edge(int u,int v,int cost,int flow)

{

	cnt++;

	Next[cnt]=Head[u];

	Head[u]=cnt;

	E[cnt].u=u;

	E[cnt].v=v;

	E[cnt].flow=flow;

	E[cnt].cost=cost;

	cnt++;

	Next[cnt]=Head[v];

	Head[v]=cnt;

	E[cnt].u=v;

	E[cnt].v=u;

	E[cnt].flow=0;

	E[cnt].cost=-cost;

}

bool spfa()

{

	for (int i=0;i<=n+1;i++)

		Dist[i]=inf;

	memset(inqueue,0,sizeof(inqueue));

	Dist[0]=0;

	inqueue[0]=1;

	int h=1,t=0;

	Q[1]=0;

	Flow[0]=inf;

	do

	{

		t++;

		int u=Q[t];

		inqueue[u]=0;

		for (int i=Head[u];i!=-1;i=Next[i])

		{

			int v=E[i].v;

			if ((E[i].flow>0)&&(Dist[u]+E[i].cost<Dist[v]))

			{

				Dist[v]=Dist[u]+E[i].cost;

				Flow[v]=min(Flow[u],E[i].flow);

				Path[v]=i;

				if (inqueue[v]==0)

				{

					h++;

					Q[h]=v;

					inqueue[v]=1;

				}

			}

		}

	}

	while(h!=t);

	if (Dist[n+1]==inf)

		return 0;

	return 1;

}