每个物品分开做最小费用最大流。
#include #include #include #include #include #include using namespace std;const int maxn=1000+10;const int INF=0x7FFFFFFF;struct Edge{ int from,to,cap,flow,cost;};int n,m,len,s,t;vector edges;vector G[maxn];int inq[maxn];int d[maxn];int p[maxn];int a[maxn];int Flag,Ans,Xu;int N,M,K;int People[55][55];int Supply[55][55];int Cost[55][55][55];void init(){ for(int i=0; i
Q; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=0; for(int i=0; i
e.flow&&d[e.to]>d[u]+e.cost) { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to]) { Q.push(e.to); inq[e.to]=1; } } } } if(d[t]==INF) return false; flow+=a[t]; cost+=d[t]*a[t]; int u=t; while(u!=s) { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u=edges[p[u]].from; } return true;}void Mincost (int s,int t){ int flow=0,cost=0; while(BellmanFord(s,t,flow,cost)); if(flow!=Xu) Flag=0; else Ans=Ans+cost;}int main(){ while(~scanf("%d%d%d",&N,&M,&K)) { if(!N&&!M&&!K) break; Flag=1; Ans=0; for(int i=1; i<=N; i++) for(int j=1; j<=K; j++) scanf("%d",&People[i][j]); for(int i=1; i<=M; i++) for(int j=1; j<=K; j++) scanf("%d",&Supply[i][j]); for(int k=1; k<=K; k++) for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d",&Cost[k][i][j]); for(int k=1; k<=K; k++) { init();s=0;t=M+M+N+1;Xu=0; for(int i=1; i<=M; i++) Addedge(s,i,INF,0); for(int i=1; i<=M; i++) Addedge(i,i+M,Supply[i][k],0); for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) Addedge(j+M,M+M+i,INF,Cost[k][i][j]); for(int i=1; i<=N; i++) Addedge(i+M+M,t,People[i][k],0); for(int i=1; i<=N; i++) Xu=Xu+People[i][k]; Mincost(s,t); if(!Flag) break; } if(Flag) printf("%d\n",Ans); else printf("-1\n"); } return 0;}