传送门 ↬\looparrowright

题目描述

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

输入格式

第一行一个正整数 nn，表示有 nn 个仓库。
第二行 nn 个正整数，表示 nn 个仓库的库存量。

输出格式

输出最少搬运量。

输入输出样例

输入 #1

5
17 9 14 16 4

输出 #1

11

说明/提示

1≤n≤1001 \leq n \leq 100。

分析

建立最小费用最大流模型。
首先设一个超级源点 ss，和一个超级汇点 tt。每个仓库和其相邻仓库之间建双向边，搬运一个货物产生的费用为 11，边的容量为 +∞+\infty。设所有仓库库存的平均值为 x‾\overline{x}，仓库 ii 的库存为 stockistock_i，货物分配完成后，每个仓库的库存都为 x‾\overline x。若 stocki>x‾stock_i>\overline{x}，可以视作超级源点 ss 向节点 ii 免费提供了流量 stocki−x‾stock_i-\overline{x}；而这部分流量是多余的，要流向 stockj<x‾stock_j<\overline x 的节点 jj，并从节点 jj 流向超级汇点 tt。因此，若 stocki>x‾stock_i>\overline x，要建立 ss 向 ii 的边，容量为 stocki−x‾stock_i-\overline x，费用为 00；若 stocki<xstock_i<x，节点 ii 流出流量 x‾−stocki\overline x-stock_i，建立 ii 向 tt 的边。
如图，边上标明了容量，最大流是 ∑i=1n[stocki>x‾](stocki−x‾)\sum\limits_{i=1}^n\left[stock_i>\overline x\right](stock_i-\overline x)，计算最小费用最大流即可。
洛谷P4016.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P4016
Date: 7/24/2020 
Description: Minimum-cost Flow
*******************************************************************/
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int N=204;
const int inf=0x3f3f3f3f;
struct E
{
	int to;
	int cap;
	int cost;
	int Next;
}edge[N*N<<1];
int tot,head[N];
int n;
int s,t;//源点 汇点
int dis[N],incf[N],pre[N];
bool inqueue[N];
int stock[N];//库存
void init();
inline void add_edge(int,int,int,int);
bool SPFA();
int MCMF();
int main()
{
	cin>>n;
	init();
	int i;
	for(i=1;i<=n;i++) scanf("%d",stock+i);
	int average=0;
	for(i=1;i<=n;i++) average+=stock[i];
	average/=n;//平均值
	for(i=1;i<=n;i++)
	{
		if(stock[i]>average) add_edge(s,i,stock[i]-average,0);
		else if(stock[i]<average) add_edge(i,t,average-stock[i],0);
	}
	for(i=1;i<=n;i++)//相邻仓库建双向边
	{
		if(i==1)
		{
			add_edge(1,n,inf,1);
			add_edge(n,1,inf,1);
		}
		else 
		{
			add_edge(i,i-1,inf,1);
			add_edge(i-1,i,inf,1);
		}
	}
	cout<<MCMF()<<endl;
	return 0;
}
void init()
{
	memset(head,-1,sizeof(head));
	s=0;
	t=n+1;
	tot=1;
}
inline void add_edge(int u,int v,int cap,int cost)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].cost=cost;
	edge[tot].Next=head[u];
	head[u]=tot;
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].cost=-cost;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool SPFA()
{
	queue<int>q;
	memset(dis,inf,sizeof(dis));
	memset(inqueue,0,sizeof(inqueue));
	q.push(s);
	dis[s]=0;
	inqueue[s]=1;
	incf[s]=inf;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inqueue[x]=0;
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			if(!edge[i].cap) continue;//剩余容量为0，不在残量网络中。
			int y=edge[i].to;
		if(dis[y]>dis[x]+edge[i].cost)
			{
				dis[y]=dis[x]+edge[i].cost;//松弛操作
				incf[y]=min(incf[x],edge[i].cap);//最小剩余容量
				pre[y]=i;//记录前驱
				if(!inqueue[y])
				{
					inqueue[y]=1;
					q.push(y);
				}
			}
		}
	}
	if(dis[t]==inf) return 0;//汇点不可达，已经求出最大流
	else return 1;
}
int MCMF()
{
	int maxflow,mincost;
	maxflow=mincost=0;
	while(SPFA())
	{
		int x=t;
		//沿着前驱倒着走增广路
		while(x!=s)
		{
			int y=pre[x];
			edge[y].cap-=incf[t];
			edge[y^1].cap+=incf[t];
			x=edge[y^1].to;
		}
		maxflow+=incf[t];
		mincost+=dis[t]*incf[t];
	}
	return mincost;
}