【POJ2516】Minimum Cost
题意：有N个收购商、M个供应商、K种物品。对于每种物品，每个供应商的供应量和每个收购商的需求量已知、每个供应商与每个收购商之间运送该物品的运费已知。求满足收购商要求的前提下的最小运费。（n,M,K<=50，每种物品供求量<=3，单位运费<=100）
题解：怎么看怎么是最小费用流，但是刚学的KM算法，还是要用一下的~
由于各种物品间没有影响，所以可以将k种物品拆开；由于供求量≤3，所以可以将供应商和收购商都拆开，然后跑KM算法。
#include#include #include using namespace std;int n,m,N,M,K,now,ret,temp,ans;int va[200],vb[200],pri[60][60][60],from[200],la[200],lb[200];int sa[60][60],sb[60][60],ba[200],bb[200],v[200][200];int dfs(int x){ va[x]=1; for(int i=1;i<=M;i++) { if(vb[i]) continue; if(la[x]+lb[i]-v[x][i]==0) { vb[i]=1; if(!from[i]||dfs(from[i])) { from[i]=x; return 1; } } else temp=min(temp,la[x]+lb[i]-v[x][i]); } return 0;}int calc(){ int i,j,ret=0; N=M=0; for(i=1;i<=n;i++) while(sa[i][now]--) ba[++N]=i; for(i=1;i<=m;i++) while(sb[i][now]--) bb[++M]=i; if(N>M) return -1; memset(la,0x80,sizeof(la)); memset(lb,0,sizeof(lb)); for(i=1;i<=N;i++) for(j=1;j<=M;j++) v[i][j]=-pri[ba[i]][bb[j]][now],la[i]=max(la[i],v[i][j]); memset(from,0,sizeof(from)); for(i=1;i<=N;i++) { while(1) { memset(va,0,sizeof(va)); memset(vb,0,sizeof(vb)); temp=1<<29; if(dfs(i)) break; if(temp==(1<<29)) return -1; for(j=1;j<=N;j++) if(va[j]) la[j]-=temp; for(j=1;j<=M;j++) if(vb[j]) lb[j]+=temp; } } for(i=1;i<=N;i++) ret+=la[i]; for(i=1;i<=M;i++) ret+=lb[i]; return -ret;}void work(){ int i,j,k; for(i=1;i<=n;i++) for(k=1;k<=K;k++) scanf("%d",&sa[i][k]); for(i=1;i<=m;i++) for(k=1;k<=K;k++) scanf("%d",&sb[i][k]); for(k=1;k<=K;k++) for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&pri[i][j][k]); ans=0; for(now=1;now<=K;now++) { k=calc(); if(k==-1) { printf("-1\n"); return ; } ans+=k; } printf("%d\n",ans);}int main(){ while(scanf("%d%d%d",&n,&m,&K)!=EOF) { if(n==0) return 0; work(); }}