问题描述:
仓库管理员M最近一直很烦恼,因为他的上司给了他一个艰难的任务:让他尽快想出一种合理的方案,把公司的仓库整理好。
已知公司共有n个仓库和n种货物,由于公司进货时没能很好的归好类,使得大部分的仓库里面同时装有多种货物,这就给搬运工作人员搬运货物时带来了很多的麻烦。
仓库管理员M的任务就是设计一种合理的方案,把仓库里面的货物重新整理,把相同的货物放到同一个仓库,以便于日后的管理,在整理过程中肯定需要把某些货物从一个仓库搬运到另一个仓库,已知每一次搬运货物所付出的代价等于搬运该货物的重量。
编程任务:
请你帮助仓库管理员M设计搬运方案,使得把所有的货物归好类:使每种货物各自占用一个仓库,或者说每个仓库里只能放一种货物。同时要求搬运货物时所付出的所有的总的代价最小。
输入:
第一行为n (1 <= n <= 150),仓库的数量。
以下为仓库货物的情况。第i+1行依次为第i个仓库中n种货物的数量x(0 <= x <= 100)。
输出:
把所有的货物按要求整理好所需的总的最小代价。
样例输入:
4
62 41 86 94
73 58 11 12
69 93 89 88
81 40 69 13
样例输出:
650
(样例说明:方案是:第1种货物放到仓库2中;第2种货物放到仓库3中;第3种货物放到仓库4中;第4种货物放到仓库1中)
题解
无脑费用流。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define T 302 #define inf 1<<30 using namespace std; int n,a[155][155],sum[155]; int zz=1,head[305]; struct bian{int to,frm,nx,v,c;} e[55000]; int dis[305],q[305],pd[305],from[305],ans; void insert(int x,int y,int z,int c) { zz++; e[zz].to=y; e[zz].frm=x; e[zz].v=z; e[zz].c=c; e[zz].nx=head[x]; head[x]=zz; zz++; e[zz].to=x; e[zz].frm=y; e[zz].v=0; e[zz].c=-c; e[zz].nx=head[y]; head[y]=zz; } void init() { scanf("%d",&n); int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) {scanf("%d",&a[i][j]); sum[j]+=a[i][j]; } for(i=1;i<=n;i++) insert(0,i,1,0); for(i=1;i<=n;i++) for(j=1;j<=n;j++) insert(i,j+n,1,sum[i]-a[j][i]); for(i=1;i<=n;i++) insert(i+n,T,1,0); } bool spfa() { memset(dis,127,sizeof(dis)); memset(pd,0,sizeof(pd)); q[0]=0; pd[0]=1; dis[0]=0; int i,x,p,t=0,w=1; while(t!=w) {x=q[t]; t=(t+1)%305; for(i=head[x];i;i=e[i].nx) {p=e[i].to; if(e[i].v>0&&dis[p]>dis[x]+e[i].c) {dis[p]=dis[x]+e[i].c; from[p]=i; if(!pd[p]) {pd[p]=1; q[w]=p; w=(w+1)%305;} } } pd[x]=0; } if(dis[T]>1000000) return false; else return true; } void mcf() { int i,x=inf; i=from[T]; while(i) {x=min(x,e[i].v); i=from[e[i].frm];} i=from[T]; while(i) {e[i].v-=x; e[i^1].v+=x; ans+=x*e[i].c; i=from[e[i].frm];} } int main() { freopen("manger.in","r",stdin); freopen("manger.out","w",stdout); init(); while(spfa()) mcf(); printf("%d",ans); return 0; }