这题意恶心得我百度了。看小悠写的看懂的*_*
各个商品的运输的代价计算是独立的，所以可以将他们分别处理
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int INF=0x7f7f7f7f; const int maxn=100008; const int maxm=58; struct fuck{ int u,v,cap,next,cost; }edge[maxn]; int head[maxm<<4]; int tol; int mpn[maxm][maxm],mpm[maxm][maxm],mpcost[maxm][maxm][maxm]; void init() { tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w,int c) { edge[tol].u=u; edge[tol].v=v; edge[tol].cap=w; edge[tol].next=head[u]; edge[tol].cost=c; head[u]=tol++; edge[tol].u=v; edge[tol].v=u; edge[tol].cap=0; edge[tol].next=head[v]; edge[tol].cost=-c; head[v]=tol++; } int micost,max_flow,last; int dis[maxm<<4],pre[maxn<<4]; bool vis[maxm<<4]; bool spfa(int sour,int sink) { queue<int> q; q.push(sour); memset(vis,false,sizeof(vis)); memset(dis,INF,sizeof(dis)); dis[sour]=0;vis[sour]=true;pre[sour]=0; int u,v,i; while(!q.empty()) { u=q.front();q.pop(); vis[u]=false; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].cap>0&&dis[v]>dis[u]+edge[i].cost) { dis[v]=dis[u]+edge[i].cost; pre[v]=i; if(!vis[v]) { q.push(v); vis[v]=true; } } } } if(dis[sink]>=INF) return false; return true; } void mincost_flow(int sour,int sink) { max_flow=0;micost=0; int i; while(spfa(sour,sink)) { int fl=INF; for(i=sink;i!=sour;i=edge[pre[i]].u) if(fl>edge[pre[i]].cap) fl=edge[pre[i]].cap; for(i=sink;i!=sour;i=edge[pre[i]].u) { edge[pre[i]].cap-=fl; edge[pre[i]^1].cap+=fl; } max_flow+=fl; micost+=dis[sink]*fl; } } int main() { int i,j,k,jj,n,m,u,v,w; while(scanf("%d%d%d",&n,&m,&k)==3) { if(n==0&&m==0&&k==0) break; bool flag=true; int ans=0; for(i=1;i<=n;i++) for(j=1;j<=k;j++) scanf("%d",&mpn[i][j]); for(i=1;i<=m;i++) for(j=1;j<=k;j++) scanf("%d",&mpm[i][j]); for(jj=1;jj<=k;jj++) for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&mpcost[jj][i][j]); for(i=1;i<=k;i++) { init(); int sum=0; for(j=1;j<=n;j++)//lingshoushang if(mpn[j][i]>0) { addedge(j,n+m+1,mpn[j][i],0); sum+=mpn[j][i]; } for(j=1;j<=m;j++)//shangjia if(mpm[j][i]>0) addedge(0,j+n,mpm[j][i],0); int sour=0,sink=n+m+1; for(j=1;j<=n;j++) { if(mpn[j][i]>0) for(jj=1;jj<=m;jj++) if(mpm[jj][i]>0) addedge(jj+n,j,mpm[jj][i],mpcost[i][j][jj]); } last=sour+1; mincost_flow(sour,sink); if(max_flow<sum) flag=false; ans+=micost; } if(flag) printf("%d ",ans); else printf("-1 "); } return 0; }