题面

题目传送

题目描述

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

输入格式

第 $1$ 行中有 $1$个正整数 $n$，表示有 $n$ 个仓库。

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

输出格式

输出最少搬运量。

思路

设平均值为 $\bar a$，$a[i]-\bar a$ 为 $b[i]$。

则对于结点 $i$，如果 $b[i]>0$ 则代表这个结点有多余的货物可以分给他人，从 $S$ 到 $i$ 连一条流量为 $b[i]$ ，费用为 $0$ 的边；

如果 $b[i]<0$ 则代表这个结点需要别人给的货物，从 $i$ 到 $T$ 连一条流量为 $-b[i]$ ($\bar a – a[i]$) ，费用为 $0$ 的边。

再从每个结点 $i$ 向环上相邻的点连流量为 $+ \infty$ ，费用为 $1$ 的边。

然后跑最小费用最大流。

因为 $\sum_{a\lbrack i\rbrack-\overline a>0}^{}a\lbrack i\rbrack-\overline a=\sum_{a\lbrack i\rbrack-\overline a<0}^{}\overline a-a\lbrack i\rbrack$ ，所以最终所有 $(i,T)$ 的边都会被填满，此时的费用即为最小。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long n,last[200005],to[200005],nextt[200005],s[200005],t[200005],top=1,ans=0,cost=0;
long long d[200005];
long long v[200005];
struct path{
    long long from,edge;
};
path p[200005];
void add(int a,int b,int c,int d){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    t[top]=d;
    last[a]=top;
}
bool spfa(long long S,long long T){
    queue<long long> q;
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    memset(p,-1,sizeof(p));
    q.push(S);
    v[S]=1;
    d[S]=0;
    d[T]=2147483647;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        for (int i=last[now];i;i=nextt[i]){
            long long j=to[i];
            if (s[i]<=0){
                continue;
            }
            if (d[now]+t[i]<d[j]){
                d[j]=d[now]+t[i];
                p[j].from=now;
                p[j].edge=i;
                if (!v[j]){
                    q.push(j);
                    v[j]=1;
                }
            }
        }
        v[now]=0;
    }
    if (d[T]<2147483647){
        return 1;
    }else{
        return 0;
    }
}
void EK(long long S,long long T){
    while (spfa(S,T)){
        long long minn=2147483647;
        for (int i=T;i!=S;i=p[i].from){
            minn=min(minn,s[p[i].edge]);
        }
        ans+=minn;
        for (int i=T;i!=S;i=p[i].from){
            s[p[i].edge]-=minn;
            s[p[i].edge^1]+=minn;
        }
        cost+=minn*d[T];
    }
}
int main(){
    long long S=105,T=106;
    int aver=0;
    cin>>n;
    int a[105];
    for (int i=1;i<=n;i++){
    	a[i]=read();
    	aver+=a[i];
	}
	aver/=n;
	for (int i=1;i<=n;i++){
		if (a[i]>aver){
	        add(S,i,a[i]-aver,0);
	        add(i,S,0,0);
		}
		if (a[i]<aver){
	        add(i,T,aver-a[i],0);
	        add(T,i,0,0);
		}
	}
	for (int i=1;i<=n;i++){
		int pre=i-1,nxt=i+1;
		if (pre==0){
			pre=n;
		}
		if (nxt==n+1){
			nxt=1;
		}
        add(i,pre,19260817,1);
        add(pre,i,0,-1);
        add(i,nxt,19260817,1);
        add(nxt,i,0,-1);
	}
    EK(S,T);
    cout<<cost;
}