Menu
Article

【SPOJ 371】球的移动 / 题解

Zepto

Zepto

• 2 min read

原题地址

题目描述

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

输入和输出

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

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

样例

输入
12
0
0
2
4
3
1
0
0
0
0
0
1
输出
19

思路

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

首先讲一下建图的方法：

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

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

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

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

代码

#include 
#define maxn 1010
using namespace std;
int head[maxn],dis[maxn];
int neflow[maxn];
int cnt=1,s,t,n,m;
struct Edge{
    int to,next,val,cost;
    Edge(int a=0,int b=0,int c=0,int d=0){
        to=a,next=b,val=c,cost=d;
    }
}l[10010];
struct Pre{
    int id,from;
    Pre(int a=0,int b=0){
        id=a,from=b;
    }
}pre[maxn];
inline void Add(int a,int b,int c,int d){
    l[++cnt]=Edge(b,head[a],c,d);head[a]=cnt;
    l[++cnt]=Edge(a,head[b],0,-d);head[b]=cnt;
}
inline bool Spfa(){
    queueq;
    fill(dis+1,dis+2+n,INT_MAX);
    q.push(s);
    dis[s]=0;
    neflow[s]=0x3f3f3f3f;
    while(!q.empty()){
        int hq=q.front();q.pop();
        for (int i=head[hq];i;i=l[i].next){
            int v=l[i].to;
            if (dis[v]>dis[hq]+l[i].cost&&l[i].val){
                dis[v]=dis[hq]+l[i].cost;
                pre[v]=Pre(i,hq);
                neflow[v]=min(neflow[hq],l[i].val);
                q.push(v);
            }
        }
    }
    return dis[t]!=INT_MAX;
}
void EK(){
    int mincost=0;
    int maxflow=0;
    while(Spfa()){
        int tem=neflow[t];
        for (register int i=t;i!=s;i=pre[i].from)
        l[pre[i].id].val-=tem,
        l[pre[i].id^1].val+=tem;
        mincost+=tem*dis[t];
        maxflow+=tem;
    }
    printf("%d",mincost);
}
int main(){
    scanf("%d",&n);
    t=n+1;
    for (register int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        Add(s,i,x,0);
        Add(i,t,1,0);
    }
    for (int i=1;i
Share