[SPOJ 371]费用流

【题目来源】http://www.spoj.pl/problems/BOXES/

【题目大意】 N个盒子围成一圈，每个盒子里有A[I]个球，每向相邻的盒子移动一个球需要花费1的代价。求，最后所有盒子至少有一个球时花费的最小代价。

【算法分析】每个盒子看成一个点
1、连边[S,I]，容量为A[I],费用为0。
2、连边[I,T]，容量为1，费用为0。
3、连边[I,I+1]，容量为inf，费用为1
4、连边[I,I-1]，容量为inf，费用为1
求最小费用最大流即可。

【其它】1A
3230300 2010-02-01 12:41:33 cwj Boxes accepted 1.17 2.9M

C++

4.3.2

【CODE】
#include #include #include #define N 1002
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,op,c,w;}g[10000];
int e,n,fa[N],d[N],ls[N],v[N],list[N],cost;

void addedge(int x,int y,int c,int w){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}   

void init(){
memset(ls,0,sizeof(ls));
e=0;
scanf("%d",&n);
for (int i=1;i<=n;i++){
int x;
scanf("%d",&x);
addedge(0,i,x,0);
addedge(i,n+1,1,0);
addedge(i,i%n+1,inf,1);
addedge(i%n+1,i,inf,1);
}
}   

bool spfa(){
for (int i=0;i<=n+1;i++){
v[i]=0;
d[i]=inf;
}   
v[0]=1; d[0]=0; list[0]=0;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].wd[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}   
}
v[list[head]]=0;
}   
if (d[n+1]==inf) return false;
return true;
}   

void change(){
cost+=d[n+1];
int nf=inf;
for (int i=n+1;i;i=g[fa[i]].x)
if (g[fa[i]].cfor (int i=n+1;i;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}   
}   

int main(){
int tc;
scanf("%d",&tc);
for (int i=0;iinit();
cost=0;
while (spfa()) change();
printf("%dn",cost);
}   
return 0;
}