传说中的网络流24题之一，我刷的第二题菜。

据说这种东西做完了就可以有质的飞越？不过看着这些Luogu评级就有点蒙蔽。

首先我们看一下题目发现这不是均分纸牌的加强板吗，但是那个环的操作极大地限制了我的思想。

我们考虑用费用流求解。

首先拆点，把每一个仓库拆成两个，一个\(x_i\)表示供给别人的货物，一个\(y_i\)表示别人供给的货物。然后建立超级源点\(S\)和超级汇点\(T\)。

我们可以很容易地知道：每一个仓库最后剩下的货物数量必定是总货物数量的平均数。

然后就很简单了。我们将所有的货物量\(a_i\)减去平均数，得到新的\(a_i\)。然后讨论：

• 当\(a_i<0\)时，这个节点需要运入货物。所以我们呢将\(S\)与\(x_i\)相连，容量就是\(-a_i\)，费用为\(0\)（至于为什么为\(0\)等下会解释）
• 当\(a_i>0\)时，这个节点需要运出货物。所以我们呢将\(y_i\)与\(T\)相连，容量就是\(a_i\)，费用为\(0\)

然后对于相邻节点还可以连边：

• 将\(x_i\)与\(y_j\)相连，容量为\(\infty\)，费用为\(1\)。这个很好理解吧，相邻的需要直接运输过去即可，费用就是运输量。
• 将\(x_i\)与\(x_j\)相连，容量为\(\infty\)，费用为\(1\)。这个还是要想一下的，相当于将\(x_i\)的货物暂时存放在\(x_j\)处，为其他的运输做准备。

然后由于所有的费用都在这些物体之间的运输中计算掉了，因此源汇点的费用就是\(0\)了。（其实也就是把那些供给的点连到一起方便跑而已，一个常见的技巧）

然后我们直接跑MCMF即可，然后引用一段著名的话：

最大流保证能够平衡货物，而最小费用流能保证运输的货物最少。

CODE

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=205,INF=2e9;

queue <int> q;

struct edge

{

    int to,next,c,f;

}e[N<<3];

int head[N],dis[N],cap[N],a[N],pre[N],last[N],s,t,n,ave,cnt=-1;

bool vis[N];

inline char tc(void)

{

    static char fl[100000],*A=fl,*B=fl;

    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

    x=0; char ch=tc();

    while (ch<'0'||ch>'9') ch=tc();

    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();

}

inline int min(int a,int b)

{

    return a<b?a:b;

}

inline void add(int x,int y,int c,int f)

{

    e[++cnt].to=y; e[cnt].c=c; e[cnt].f=f; e[cnt].next=head[x]; head[x]=cnt;

}

inline void insert(int x,int y)

{

    add(x,y,INF,1); add(y,x,0,-1); add(x,y+n,INF,1); add(y+n,x,0,-1);

}

inline bool SPFA(void)

{

    memset(pre,-1,sizeof(pre));

    memset(dis,63,sizeof(dis));

    memset(cap,63,sizeof(cap));

    memset(vis,0,sizeof(vis));

    while (!q.empty()) q.pop();

    q.push(s); vis[s]=1; dis[s]=0;

    while (!q.empty())

    {

        int now=q.front(); q.pop(); vis[now]=0;

        for (register int i=head[now];i!=-1;i=e[i].next)

        if (e[i].c&&dis[e[i].to]>dis[now]+e[i].f)

        {

            dis[e[i].to]=dis[now]+e[i].f;

            cap[e[i].to]=min(cap[now],e[i].c);

            pre[e[i].to]=now; last[e[i].to]=i;

            if (!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);

        }

    }

    return pre[t]^-1;

}

inline void MCMF(void)

{

    int tot=0;

    while (SPFA())

    {

        tot+=cap[t]*dis[t]; int now=t;

        while (now!=s)

        {

            e[last[now]].c-=cap[t];

            e[last[now]^1].c+=cap[t];

            now=pre[now];

        }

    }

    printf("%d",tot);

}

int main()

{

    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

    register int i; read(n); s=0,t=(n<<1)+1;

    memset(head,-1,sizeof(head));

    memset(e,-1,sizeof(e));

    for (i=1;i<=n;++i)

    read(a[i]),ave+=a[i]; ave/=n;

    for (i=1;i<=n;++i)

    {

        a[i]-=ave; if (a[i]>0) add(s,i,a[i],0),add(i,s,0,0); else add(i+n,t,-a[i],0),add(t,i+n,0,0);

        if (i==1) insert(1,n),insert(1,2); else

        if (i==n) insert(n,1),insert(n,n-1); else insert(i,i-1),insert(i,i+1);

    }

    MCMF(); return 0;

}