原题地址

题目描述

有 $n$ 个盒子($1<=N<=1000$)围成一个圈,每个盒子有 $a_i$ 个球,所有盒子的球的总数小于等于 $n$。每一次移动,可以把一个球移动到它的一个相邻的盒子内。 现在要使得每个盒子的球数 $<=1$,求最少的移动次数。

输入和输出

输入的第一行为一个整数 $n$。接下来 $n$ 行,每行一个整数 $a_i$,代表第 $i$ 个盒子里球的个数。

输出一个整数,代表最少的移动次数。

样例

输入

输出

思路

练习网络流的一道题,做完令我对费用流有了更深层次的理解。。。

首先讲一下建图的方法:

超级源点到每个盒子建立一条流量为 $a_i$,费用为 0 的边;
每对相邻的盒子之间建立一条流量为无限,费用为 1 的边;
最后每个盒子到超级汇点建立一条流量为 $1$ ,费用为 0 的边。

在这张图上求最小费用最大流即可。

然后如果你不够理解其中的原因,可以这样理解:

我们将球的移动看做流量,费用为操作次数。初始从源点流出到每个盒子的流量显然就是球的个数 $a_i$,费用为 0。因为我们允许进行的操作是在相邻的盒子之间移动一个球,所以相邻盒子之间建立流量为无限(因为这个操作理论上可以进行无限次),费用为 1 的边。最后因为最后每个盒子只能留下小于等于 1 的球,所以连向汇点的边流量只能为 1。

代码