GGG 公司有 nnn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nnn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
文件的第 111 行中有 111 个正整数 nnn ，表示有 nnn 个仓库。
第 222 行中有 nnn 个正整数，表示 nnn 个仓库的库存量。
输出最少搬运量。
5 17 9 14 16 4
11
1≤n≤1001 \leq n \leq 1001≤n≤100
/10min一遍A 2333
考虑使用费用流。
超级源到每个点流量为点权，代价为0
每个点到相邻的点流量为INF，代价为1
每个点到超级汇流量为点权平均值，代价为0
还蛮好想的。
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int INF=99999999; struct emm{ int e,f,v,c; }a[100007]; int h[107]; int tot=1; void con(int u,int v,int w,int f) { a[++tot].f=h[u]; h[u]=tot; a[tot].e=v; a[tot].v=w; a[tot].c=f; a[++tot].f=h[v]; h[v]=tot; a[tot].e=u; a[tot].c=-f; return; } int d[107]; bool sf[107]; int n,s,t; queue<int>q; bool spfa() { memset(sf,0,sizeof(sf)); memset(d,127,sizeof(d)); sf[s]=1;d[s]=0;q.push(s); while(!q.empty()) { int x=q.front();q.pop(); for(int i=h[x];i;i=a[i].f) if(d[a[i].e]>d[x]+a[i].c&&a[i].v) { d[a[i].e]=d[x]+a[i].c; if(!sf[a[i].e]) { sf[a[i].e]=1; q.push(a[i].e); } } sf[x]=0; } return d[t]<INF; } int ans=0; int dfs(int x,int al) { sf[x]=1; if(x==t||!al)return al; int fl=0; for(int i=h[x];i;i=a[i].f) if(d[a[i].e]==d[x]+a[i].c&&a[i].v&&!sf[a[i].e]) { int f=dfs(a[i].e,min(al,a[i].v)); if(f) { fl+=f; al-=f; ans+=f*a[i].c; a[i].v-=f; a[i^1].v+=f; if(!al)break; } } if(!fl)d[x]=-1; return fl; } int main() { scanf("%d",&n); s=0,t=n+1; int sum=0; for(int i=1;i<=n;++i) { int x; scanf("%d",&x); con(s,i,x,0); sum+=x; } sum/=n; for(int i=1;i<n;++i) { con(i,i+1,INF,1); con(i+1,i,INF,1); } con(1,n,INF,1); con(n,1,INF,1); for(int i=1;i<=n;++i) con(i,t,sum,0); while(spfa()) { sf[t]=1; while(sf[t]) { memset(sf,0,sizeof(sf)); dfs(s,INF); } } cout<<ans; return 0; }转载于:https://www.cnblogs.com/qwerta/p/9379735.html
