题目描述 Description
G 公司有n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最
少搬运量可以使n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
«编程任务：
对于给定的n 个环形排列的仓库的库存量，编程计算使n 个仓库的库存数量相同的最少
搬运量。
输入描述 Input Description
第1 行中有1 个正整数n（n<=100），表示有n
个仓库。第2 行中有n个正整数，表示n个仓库的库存量。
输出描述 Output Description
将计算出的最少搬运量输出
样例输入 Sample Input
5
17 9 14 16 4
样例输出 Sample Output
11
建图很简单
先计算出平均值，如果多了就从s向它连一条容量为差值费用为0的边，如果少了就向t连一条容量为差值费用为0的边
然后每个点向旁边两个点连一条容量为inf费用为1的边，然后跑最小费用最大流就行了（一开始傻叉的把一个点拆成了两个点）
1 const 2 inf=100000; 3 maxn=105; 4 type 5 path=record 6 next,last,w,c:longint; 7 end; 8 var 9 edge:array[0..maxn*8]of path; 10 first:array[0..maxn]of longint; 11 a:array[0..maxn]of longint; 12 n,tot,s,t:longint; 13 14 procedure insert(x,y,c,w:longint); 15 begin 16 inc(tot); 17 edge[tot].next:=first[x]; 18 edge[tot].last:=y; 19 edge[tot].w:=w; 20 edge[tot].c:=c; 21 first[x]:=tot; 22 inc(tot); 23 edge[tot].next:=first[y]; 24 edge[tot].last:=x; 25 edge[tot].w:=-w; 26 edge[tot].c:=0; 27 first[y]:=tot; 28 end; 29 30 procedure init; 31 var 32 i,sum:longint; 33 begin 34 read(n); 35 tot:=1; 36 s:=0; 37 t:=n+1; 38 sum:=0; 39 for i:=1 to n do 40 begin 41 read(a[i]); 42 inc(sum,a[i]); 43 end; 44 sum:=sum div n; 45 for i:=1 to n do 46 begin 47 if a[i]>sum then insert(i,t,a[i]-sum,0); 48 if a[i]<sum then insert(s,i,sum-a[i],0); 49 end; 50 for i:=1 to n do 51 begin 52 insert(i,i mod n+1,inf,1); 53 insert(i mod n+1,i,inf,1); 54 end; 55 end; 56 57 var 58 flow,time,ans:longint; 59 flag,dis,f:array[0..maxn]of longint; 60 61 function dfs(x,flow:longint):longint; 62 var 63 i,d,min:longint; 64 begin 65 if x=t then 66 begin 67 inc(ans,flow*dis[t]); 68 exit(flow); 69 end; 70 flag[x]:=time; 71 i:=first[x]; 72 dfs:=0; 73 while i<>0 do 74 begin 75 d:=dis[x]+edge[i].w-dis[edge[i].last]; 76 min:=flow; 77 if min>edge[i].c then min:=edge[i].c; 78 if (min>0) and (d<f[edge[i].last]) then f[edge[i].last]:=d; 79 if (min>0) and (d=0) and (flag[edge[i].last]<>time) then 80 begin 81 d:=dfs(edge[i].last,min); 82 inc(dfs,d); 83 dec(flow,d); 84 inc(edge[i xor 1].c,d); 85 dec(edge[i].c,d); 86 end; 87 if flow=0 then break; 88 i:=edge[i].next; 89 end; 90 end; 91 92 procedure work; 93 var 94 i,del:longint; 95 begin 96 repeat 97 inc(time); 98 for i:=1 to t do 99 f[i]:=inf; 100 inc(flow,dfs(s,inf)); 101 del:=inf; 102 for i:=1 to t do 103 if (flag[i]<>time) and (del>f[i]) then del:=f[i]; 104 if del=inf then break; 105 for i:=1 to t do 106 if flag[i]<>time then inc(dis[i],del); 107 until false; 108 write(ans); 109 end; 110 111 begin 112 init; 113 work; 114 end.