有n个盒子(1<=N<=1000)围成一个圈,每个盒子有ai个球,所有盒子的球的总数小于等于n.每一次移动,可以把一个球移动到它的一个相邻的盒子内.
现在要使得每个盒子的球数<=1,求最少的移动次数
输入格式：
na1
a2
…
an
输出格式：
最少移动次数样例输入：
12 0 0 2 4 3 1 0 0 0 0 0 1
样例输出：
19
网络流真乃xjb题的解题法宝
费用流。先设超级源点0和超级汇点2*n+1，然后将每个点拆成源点和汇点，然后每个源点先与对应汇点连一条容量无限大，费用为0的边；然后与相邻点的汇点连容量无限大，费用为1的边，最后将各源点与超级源点连一条容量为a[i]费用为0的边，各汇点与超级汇点连一条容量为1费用为0的边，然后跑一遍费用流即可。（为什么？自己思考吧）
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct edge{ int v,c,f; }e[100010]; int fi[100010],ne[100010],la[100010],q[200020],d[100010],flow[100010],x,ansflow,anscost,tot,pe[100010],n,m,s,t,b[200010],pre[200010],u,v,w,f; void add(int x,int y,int f,int c){ e[++tot].v=y;e[tot].c=c;e[tot].f=f; !fi[x]?fi[x]=tot:ne[la[x]]=tot;la[x]=tot; e[++tot].v=x;e[tot].c=-c;e[tot].f=0; !fi[y]?fi[y]=tot:ne[la[y]]=tot;la[y]=tot; } bool spfa(int s,int t){ int H=0,T=0; memset(d,0x3f,sizeof(d)); memset(flow,0,sizeof(flow)); q[++T]=s;b[s]=1;d[s]=0;pre[s]=0;flow[s]=0x7fffffff; while(H<T){ int x=q[++H]; for(int i=fi[x];i;i=ne[i]){ int y=e[i].v,z=e[i].f,c=e[i].c; if(z>0&&d[y]>d[x]+c){ d[y]=d[x]+c; pre[y]=x; pe[y]=i; flow[y]=min(flow[x],z); if(!b[y])b[y]=1,q[++T]=y; } } b[x]=0; } return d[t]!=0x3f3f3f3f; } void maxflow(){ while(spfa(s,t)){ int k=t; while(k!=s){ e[pe[k]].f-=flow[t]; e[pe[k]^1].f+=flow[t]; k=pre[k]; } ansflow+=flow[t]; anscost+=d[t]*flow[t]; } } int main(){ scanf("%d",&n); tot=1; for(int i=1;i<=n;i++){ scanf("%d",&x); int pr=i==1?n:i-1,nx=i==n?1:i+1; add(0,i,x,0); add(i,nx+n,0x3f3f3f3f,1); add(nx+n,i,0x3f3f3f3f,1); add(i,pr+n,0x3f3f3f3f,1); add(pr+n,i,0x3f3f3f3f,1); add(i,i+n,0x3f3f3f3f,0); add(i+n,i,0x3f3f3f3f,0); add(i+n,2*n+1,1,0); } s=0;t=2*n+1; maxflow(); printf("%d",anscost); }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
