[最小费用流]hdoj 2282：Chocolate
大致题意：
? ? 有n个巧克力盒子摆成一圈，每个盒子中装有一定数量的巧克力，所有盒子中的巧克力的总数小于n。现在每次可以把一块巧克力从一个盒子移动到其相邻的盒子中，求最少移动几部才能使得每个盒子中最多只有一个巧克力。
?
大致思路：
? ? 很经典的构图。设源汇点，将每个盒子拆为两点a，a'。从源点想s连边，容量为盒子中巧克力的数量，费用为0。从 ? ? ? ? a->b'连边，容量为1，费用为0。对于两个盒子ab，如果a中的数量大于1，b中的数量等于0.则连接a->b'，容量为1，费用为两个盒子之间的最短距离。a'向汇点连边，容量为1，费用为0。求出最小费用就是答案。
?
#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int inf=99999999;const int nMax=3000;const int mMax=2000000;struct{ int u,v, cap, cost, next, re;}edge[mMax];int ans,maxf;int k,edgeHead[nMax];int que[nMax],pre[nMax],dis[nMax];bool vis[nMax],flag;int K;void addEdge(int u,int v,int ca,int co){////始点 终点 流量 花费 edge[k].v=v; edge[k].cap=ca; edge[k].cost=co; edge[k].next=edgeHead[u]; edge[k].re=k + 1; edgeHead[u]=k ++; edge[k].v=u; edge[k].cap=0; edge[k].cost=-co; edge[k].next=edgeHead[v]; edge[k].re=k - 1; edgeHead[v]=k ++;}bool spfa(int s,int t,int n){ //始点，终点，总点数 int i, head = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方 for(i = 0; i <= n; i ++){ dis[i] = inf;//////////// vis[i] = false; } dis[s] = 0; que[0] = s; vis[s] = true; while(head != tail){ int u = que[head]; for(i = edgeHead[u]; i != 0; i = edge[i].next){ int v = edge[i].v; if(edge[i].cap && dis[v] >dis[u] + edge[i].cost){//////// dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]){ vis[v] = true; que[tail ++] = v; if(tail == nMax) tail = 0; } } } vis[u] = false; head++; if(head ==nMax) head = 0; } if(dis[t] ==inf) return false;/////////// return true;}void end(int s,int t){ int u, p; for(u = t;u!=s;u=edge[edge[p].re].v){ p = pre[u]; edge[p].cap-=1; edge[edge[p].re].cap+=1; ans+=edge[p].cost; } maxf+=1; //总流量}int box[nMax];int abs(int a){ if(a>0) return a; return -a;}int main(){ int n,i,j,s,t; while(scanf("%d",&n)!=EOF){ s=0,t=2*n+1; k=1; memset(edgeHead,0,sizeof(edgeHead)); for(i=1;i<=n;i++){ scanf("%d",&box[i]); if(box[i]!=0)addEdge(s,i,box[i],0); addEdge(i,i+n,1,0); addEdge(i+n,t,1,0); } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(i==j||box[i]==0||box[j]!=0)continue; addEdge(i,j+n,1,min(abs(i-j),n-abs(j-i))); } } ans=maxf=0; while(spfa(s,t,2*n+2)){ end(s,t); } printf("%d\n",ans); } return 0;}?