建模比较简单：
求出平均数tp。
让S连向 a[i]>tp的节点表示这些仓库需要货物送出，让a[i]<tp的节点连向T表示这些仓库需要货物送入。容量为差值，花费为0
然后相邻点连边，容量为inf，花费为1，表示相邻两点可以传送货物。
一下是最小费用最大流的两种写法对比：
当图是稀疏图时，spfa有很高的效率，而稠密图spfa很容易被卡掉。视情况选择就行。
dij版本
#include<bits/stdc++.h>
using namespace std;
const int N = 5001;
const int M = 50001;
struct MCMF
{ int n, s, t, cnt = 1;long long maxflow=0, mincost=0;int dis[N], head[N], incf[N], pre[N];//dis表示最短路，incf表示当前增广路上最小流量，pre表示前驱bool vs[N];int h[N];//dij中的势能 struct EDGE {int nxt, to, flow,cost;}ee[M << 1];inline void AD(int x, int y, int flow, int cost) {ee[++cnt].nxt = head[x];ee[cnt].to = y;ee[cnt].cost = cost;ee[cnt].flow = flow;head[x] = cnt;}inline void add(int x, int y, int flow, int cost){AD(x,y,flow,cost);AD(y,x,0,-cost);//双向边 }inline bool Dijkstra() {priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >q;for(; !q.empty(); q.pop());memset(dis,0x3f,sizeof(dis));memset(vs,0,sizeof(vs));dis[s]=0;incf[s] = 0x3f3f3f3f;q.push({dis[s],s});while(!q.empty()){pair<int,int> tp=q.top();q.pop();int u=tp.second ;if(vs[u])continue;vs[u]=1;for(int i=head[u];i;i=ee[i].nxt){int v=ee[i].to,cost=ee[i].cost,flow=ee[i].flow;if(!flow)continue;//没有剩余流量 if(dis[v]>dis[u]+cost+h[u]-h[v]){dis[v]=dis[u]+cost + h[u] - h[v];q.push({dis[v],v});incf[v] = min(incf[u], flow);//更新incfpre[v]=i;//记录路径 }}}if(dis[t] == 0x3f3f3f3f) return 0;return 1;}void gao() {while(Dijkstra()) {//如果有增广路for(int i=1;i<=n;i++)if(dis[i]!=0x3f3f3f3f)h[i]+=dis[i];int x = t;maxflow += incf[t];mincost += (long long)h[t] * incf[t];int i;while(x != s) {//遍历这条增广路，正向边减流反向边加流i = pre[x];ee[i].flow -= incf[t];ee[i^1].flow += incf[t];x = ee[i^1].to;}}}//先初始化 void init(int nn,int S,int T){n=nn,s=S,t=T;cnt=1;for(int i=0;i<=n;i++)head[i]=0,h[i]=0;//势能清零 mincost=maxflow=0;}
}mc;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,m,s,t;cin>>n; int u,v,w,x;s=n+1,t=n+2;mc.init(n+2,s,t);int sm=0;for(int i=1;i<=n;i++){cin>>a[i];sm+=a[i];}sm/=n;int inf=0x3f3f3f3f;for(int i=1;i<=n;i++){if(a[i]>sm)mc.add(s,i,a[i]-sm,0);if(a[i]<sm)mc.add(i,t,sm-a[i],0);if(i<n)mc.add(i,i+1,inf,1),mc.add(i+1,i,inf,1);else mc.add(i,1,inf,1),mc.add(1,i,inf,1);}mc.gao();//最小费用最大流printf("%lld\n",mc.mincost);return 0;
}SPFA版
//spfa
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5001;
const int MAXM = 50001;
struct MCMF
{ int n, s, t, cnt = 1;long long maxflow=0, mincost=0;int dis[MAXN], head[MAXN], incf[MAXN], pre[MAXN];//dis表示最短路，incf表示当前增广路上最小流量，pre表示前驱bool vis[MAXN];struct EDGE {int next, to, dis, flow;}ee[MAXM << 1];inline void AD(int from, int to, int flow, int dis) {ee[++cnt].next = head[from];ee[cnt].to = to;ee[cnt].dis = dis;ee[cnt].flow = flow;head[from] = cnt;}inline void add(int x, int y, int flow, int cost){AD(x,y,flow,cost);AD(y,x,0,-cost);//双向边 }inline bool spfa() {queue <int> q;for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f,vis[i]=0; q.push(s);dis[s] = 0;vis[s] = 1;incf[s] = 0x3f3f3f3f;while(!q.empty()) {int u = q.front();vis[u] = 0;q.pop();for(register int i = head[u]; i; i = ee[i].next) {if(!ee[i].flow) continue;//没有剩余流量int v = ee[i].to;if(dis[v] > dis[u] + ee[i].dis) {dis[v] = dis[u] + ee[i].dis;incf[v] = min(incf[u], ee[i].flow);//更新incfpre[v] = i;if(!vis[v]) vis[v] = 1, q.push(v);}}}if(dis[t] == 0x3f3f3f3f) return 0;return 1;}void gao() {while(spfa()) {//如果有增广路int x = t;maxflow += incf[t];mincost += (long long)dis[t] * incf[t];int i;while(x != s) {//遍历这条增广路，正向边减流反向边加流i = pre[x];ee[i].flow -= incf[t];ee[i^1].flow += incf[t];x = ee[i^1].to;}}}//先初始化 void init(int nn,int S,int T){n=nn,s=S,t=T;cnt=1;for(int i=0;i<=n;i++)head[i]=0;mincost=maxflow=0;}
}mc;
int a[MAXN];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,m,s,t;cin>>n; int u,v,w,x;s=n+1,t=n+2;mc.init(n+2,s,t);int sm=0;for(int i=1;i<=n;i++){cin>>a[i];sm+=a[i];}sm/=n;int inf=0x3f3f3f3f;for(int i=1;i<=n;i++){if(a[i]>sm)mc.add(s,i,a[i]-sm,0);if(a[i]<sm)mc.add(i,t,sm-a[i],0);if(i<n)mc.add(i,i+1,inf,1),mc.add(i+1,i,inf,1);else mc.add(i,1,inf,1),mc.add(1,i,inf,1);}mc.gao();//最小费用最大流printf("%lld\n",mc.mincost);return 0;
}