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]>)
add(S,i,map[i]-,);
else if(!map[i])
add(i,T,,);
add(i,(i==)?n:i-,INF,);
add(i,(i==n)?:i+,INF,);
}
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 ...

  9. scrapy adopt FormRequest Simulate login and continue

    1. Reference resources https://doc.scrapy.org/en/latest/topics/spiders.html#scrapy.spiders.Spider.start_requests Automatic submission ...

  10. int __get_order(unsigned long size)

    2017-12-6 10:26:504.9.51int __get_order(unsigned long size){    int order; size--;    size >>= ...