N A box in a circle , The first i The first box had Ai A little ball , You can move a ball from one box to one of the two adjacent boxes at a time . How many times should I move at least so that the number of balls in each box does not exceed 1.

ΣAi<=N.1<=N<=1000.

Minimum cost and maximum flow .

Each box serves as a point .

if Ai>1 Then from the source point to this point, connect a line with the capacity of Ai, The cost is 0 The edge of .

if Ai=0 From this point to the sink point, connect a line with a capacity of 1, The cost is 0 The edge of .

Each box has a positive infinity to two adjacent boxes , The cost is 1 The edge of .

Minimum cost and maximum flow is the answer .

``` #include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int dian=;
const int bian=;
const int INF=0x3f3f3f3f;
int h[dian],nxt[bian],ver[bian],val[bian],cos[bian],with[dian],minn[dian];
int d[dian],v[dian];
int map[dian];
int n,tot;
int S,T;
void add(int a,int b,int c,int d){
tot++;ver[tot]=b;val[tot]=c;cos[tot]=d;nxt[tot]=h[a];h[a]=tot;
tot++;ver[tot]=a;val[tot]=;cos[tot]=-d;nxt[tot]=h[b];h[b]=tot;
}
bool tell(){
memset(v,,sizeof(v));
memset(d,0x3f,sizeof(d));
memset(with,,sizeof(with));
memset(minn,0x3f,sizeof(minn));
queue<int>q;
q.push(S);
v[S]=;
d[S]=;
while(!q.empty()){
int x=q.front();
q.pop();
v[x]=;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(d[y]>d[x]+cos[i]&&val[i]){
d[y]=d[x]+cos[i];
minn[y]=min(minn[x],val[i]);
with[y]=i;
if(!v[y]){
v[y]=;
q.push(y);
}
}
}
}
if(d[T]==0x3f3f3f3f)
return ;
return ;
}
int zeng(){
for(int i=T;i!=S;i=ver[with[i]^]){
val[with[i]]-=minn[T];
val[with[i]^]+=minn[T];
}
return minn[T]*d[T];
}
int dinic_cost(){
int r=;
while(tell())
r+=zeng();
return r;
}
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
memset(h,,sizeof(h));
memset(nxt,,sizeof(nxt));
tot=;
scanf("%d",&n);
S=n+,T=n+;
for(int i=;i<=n;i++)
scanf("%d",&map[i]);
for(int i=;i<=n;i++){
if(map[i]>)
else if(!map[i])
}
printf("%d\n",dinic_cost());
}
return ;
}```

## spoj 371 Boxes More articles about

1. spoj 371 Boxes【 Minimum cost and maximum flow 】

about ai==0 Connect (i,t,1,0), about ai>1(s,i,ai-1,0), And then two adjacent points (i,j) Connect (i,j,inf,1), Notice that this is in the form of a ring , therefore 1 and n+1 Connected to a #include ...

2. [ turn ] POJ Introduction to graph theory

There are not many types of shortest path problems , Less deformation POJ 2449 Remmarguts' Date( secondary )http://acm.pku.edu.cn/JudgeOnline/problem?id=2449 The question : ...

3. One of the common algorithms in graph theory POJ The problem set of graph theory 【 Reprint 】

POJ Graph theory classification [ turn ] A very good graph theory classification , Thank you very much for the original author !!! Share it here , Like graph theory ACMer No more loneliness ... ( I'm sorry I didn't find the original author of this collection , Thank you for your original link ) POJ:h ...

4. SPOJ BOXES

give n It's a circular position , There are a certain number of boxes in each position , Each operation can move a box to an adjacent location , Ask at least how many times you need to transfer so that the number of boxes in all positions does not exceed 1 individual . Simple questions . For each location , Bordering (s,i,a[i],0),(i ...

5. BZOJ 2588: Spoj 10628. Count on a tree [ Chairman tree on the tree ]

2588: Spoj 10628. Count on a tree Time Limit: 12 Sec  Memory Limit: 128 MBSubmit: 5217  Solved: 1233 ...

6. SPOJ DQUERY D-query（ Chairman tree ）

subject Source http://www.spoj.com/problems/DQUERY/en/ Description Given a sequence of n numbers a1, a2, ...

7. SPOJ GSS3 Can you answer these queries III[ Line segment tree ]

SPOJ - GSS3 Can you answer these queries III Description You are given a sequence A of N (N <= 50 ...

8. Fedora 24 Gnome Boxes unable ping Communication network

install Fedora 24 When trying out the virtual machine, we found that we couldn't ping Internet access . I thought it was a software problem . Problem description : Try ping Program to test network connectivity : ( I was before, too ping Baidu , Later in order to less typing Baidu a number of relatively short domain names ...

9. 【 Fill the hole to 】spoj COT/bzoj2588 Count on a tree

This is a question I wanted to write when I was studying the chairman tree ,,, But I didn't write ( lazy ) Now fill the hole = = Daily tune half a day lca( Think about it later ) The chairman tree is very easy to write , But the code repeats , Not so good , Lead to debugging when the bottom of my heart ( Although it turns out that the chairman tree part ...

## Random recommendation

1. Mysql Learning notes （ Four ） Let's talk about database index

Little mood ( You can jump directly behind the split line ) I feel better today . Some strong bad emotions that can't be changed , Gradually, after solving a complicated logic problem at night , Gradually dissipated . When I went for lunch today , Brother Kun said carelessly :' After all these years, I finally realized a truth , people ...

2. C The data type of language and its corresponding variable

Statement , Definition and initialization Declaration identifier iden Tell the compiler " There is such a variable var, Specifically var What's in it , Go and see for yourself ". Declaration requires only the type and name of the identifier ,C Any identifier of a language needs to be declared before it can be used ...

3. ubuntu12.04 Configure static IP And settings DNS

static state IP Configuration method : edit /etc/network/interfaces, Delete the content , And enter the following lines ( Suppose your network card is eth0) sudo gedit /etc/network/interfaces aut ...

4. Motan Learning begins

You've come here , Just walk patiently in the back .   -- anonymous After entering the new company , Company use dubbo frame , After a simple picture of gourd and ladle , It's a start , But I don't understand the internal implementation mechanism . I'm just curious , I feel that every ...

5. SpringMVC from Control Medium response json data

Get it asynchronously on the page Controller In response to json data . <%@ page language="java" contentType="text/html; cha ...

6. Android Life cycle method when cutting horizontal and vertical screens ？222

Case one : Not set up Activity Of android:configChanges when , Cutting the screen will recall each life cycle , It will be executed once when cutting the horizontal screen , When cutting the vertical screen, it will execute twice The second case : Set up Activity Of androi ...

7. vim - manual - Personal notes

##vim To configure ###normal > Enter the command :w Write save > > Paste :p( Paste down ) P( Paste capital up ) > > Copy :yy Duplicate a row > > Delete ...

8. 2025 strategic , Mid Autumn Festival send Welfare ！ Free and open source ERP Odoo Windows One click fool installation release

summary In order to help more Xiaobai , Be able to experience quickly Odoo The power of , For most domestic Xiaobai users, they can't experience it quickly and directly Odoo Embarrassment , Open source intelligent manufacturing makes great efforts , After hundreds of tests and integrations, we will finally catch up with the Mid Autumn Festival Odoo Complex operating loops required ...