首页 > 代码库 > poj 2516 Minimum Cost KM或最小费用流
poj 2516 Minimum Cost KM或最小费用流
题意:
有k种物品,n个商店和m个供应站,每个商店对每种商品有需求量shopNeed[n][k],每个供应站对每种商品都有存货量supply[m][k],对于种类k的物品,他从供应站j到商店i的花费为cost[k][i][j],求让每个商店每种商品满足需求量的最小花费。
分析:
典型的最小费用最大流问题,但因为每种商品的需求量和存货量都很小(<=3),每个点拆成的新点也少,故可以用拆点+KM的方法做。
代码:
//poj 2516 //sep9 #include <iostream> using namespace std; const int maxN=220; int w[maxN][maxN]; int mapX[maxN],mapY[maxN]; int lx[maxN],ly[maxN],linky[maxN]; int visx[maxN],visy[maxN]; int slack[maxN]; int nx,ny,n,m,k; int shopNeed[maxN][maxN]; int supply[maxN][maxN]; int cost[maxN][maxN][maxN]; bool find(int x) { visx[x]=true; for(int y=1;y<=ny;++y){ if(visy[y]) continue; int t=lx[x]+ly[y]-w[x][y]; if(t==0){ visy[y]=true; if(linky[y]==-1||find(linky[y])){ linky[y]=x; return true; } } else if(slack[y]>t) slack[y]=t; } return false; } int KM() { int i,j; memset(linky,-1,sizeof(linky)); memset(ly,0,sizeof(ly)); for(i=1;i<=nx;++i) for(j=1,lx[i]=INT_MIN;j<=ny;++j) if(w[i][j]>lx[i]) lx[i]=w[i][j]; for(int x=1;x<=nx;++x){ for(i=1;i<=ny;++i) slack[i]=INT_MAX; while(1){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(find(x)) break; int d=INT_MAX; for(i=1;i<=ny;++i) if(!visy[i]&&slack[i]<d) d=slack[i]; if(d==INT_MAX) return 1; for(i=1;i<=nx;++i) if(visx[i]) lx[i]-=d; for(i=1;i<=ny;++i) if(visy[i]) ly[i]+=d; else slack[i]-=d; } } int result=0; for(i=1;i<=ny;++i) if(linky[i]>-1) result+=w[linky[i]][i]; return result; } int main() { while(scanf("%d%d%d",&n,&m,&k)==3){ if(n==0&&m==0&&k==0) break; int i,j,t; for(i=1;i<=n;++i) for(t=1;t<=k;++t) scanf("%d",&shopNeed[i][t]); for(j=1;j<=m;++j) for(t=1;t<=k;++t) scanf("%d",&supply[j][t]); for(t=1;t<=k;++t) for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%d",&cost[t][i][j]); int ans=0,p,q; for(t=1;t<=k;++t){ nx=0;ny=0; for(i=1;i<=n;++i) for(p=1;p<=shopNeed[i][t];++p) mapX[++nx]=i; for(j=1;j<=m;++j) for(q=1;q<=supply[j][t];++q) mapY[++ny]=j; for(i=1;i<=nx;++i) for(j=1;j<=ny;++j) w[i][j]=-cost[t][mapX[i]][mapY[j]]; int x=KM(); if(x>0){ ans=-1; break; } else ans-=x; } printf("%d\n",ans); } return 0; }
poj 2516 Minimum Cost KM或最小费用流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。