/* 有N个连锁店,M供货商,供应K中物品,然后还有 某供货商 向 某连锁店 供应 某种物品 的费用 输入格式是: N M K N行,每行K个,表示 某连锁店 对于 某物品 的需求 M行,每行K个,表示 某供货商 关于 某物品 的储量 K个矩阵,每个矩阵N行,M列,表示 某物品 由 某供货商 向 某连锁店 供货的费用 输出最小费用,若无法满足,输出-1 分别对K中物品进行最小费用最大流就行了 在调试本代码的过程中,终于体会到"现在早上5点,那指针现在指向哪儿?"是多么... */ #include<iostream> #include<queue> using namespace std; class solve { public: int n,m,k; int mincost; int** xuqiu; int** gy; int*** fee; int** flow; int** hua; int s,t; int* pre; int* dist; int* vis; void du() { int i,j,h; xuqiu=new int*[n+1]; for(i=1;i<=n;++i) { xuqiu[i]=new int[k+1]; for(j=1;j<=k;++j) cin>>xuqiu[i][j]; } gy=new int*[m+1]; for(i=1;i<=m;++i) { gy[i]=new int[k+1]; for(j=1;j<=k;++j) cin>>gy[i][j]; } fee=new int**[k+1]; for(i=1;i<=k;++i) { fee[i]=new int*[n+1]; for(j=1;j<=n;++j) { fee[i][j]=new int[m+1]; for(h=1;h<=m;++h) cin>>fee[i][j][h]; } } } solve(int nn,int mm,int kk):n(nn),m(mm),k(kk) { int i; s=0; t=n+m+1; mincost=-1; du(); chu(); if(!manzu()) { printf("%d\n",mincost); return; } mincost=0; for(i=1;i<=k;++i) { zhuru(i); jiejue(i); } printf("%d\n",mincost); } void jiejue(int w) { while(spfa()) add(); } int spfa()//求费用最小的改进路径 { dist[s]=0; for(int i=1;i<n+m+2;i++) dist[i]=inf(); vis[s]=1; queue<int>q; q.push(s); while(!q.empty()) { int u=q.front(); for(int v=0;v<=t;++v) { if(flow[u][v]&&dist[v]>dist[u]+hua[u][v]) { dist[v]=dist[u]+hua[u][v]; pre[v]=u; if(!vis[v]) { q.push(v); vis[v]=1; } } } q.pop(); vis[u]=0; } if(dist[t]==inf()) return 0; return 1; } void add()//压入流 { int MaxFlow=inf(); int i; for(i=t;i!=s;i=pre[i]) MaxFlow=min(MaxFlow,flow[pre[i]][i]); for(i=t;i!=s;i=pre[i]) { flow[pre[i]][i]-=MaxFlow; flow[i][pre[i]]+=MaxFlow; mincost+=hua[pre[i]][i]*MaxFlow; } return; } int inf() const{return 0x7FFFFFFF;}//设最大值 int min(int a,int b) {return a<b?a:b;}//取较小的 void zhuru(int w) { int i,j; for(i=0;i<n+m+2;++i) { memset(flow[i],0,sizeof(int)*(n+m+2)); memset(hua[i],0,sizeof(int)*(n+m+2)); } for(i=1;i<=m;++i) flow[0][i]=gy[i][w]; for(i=1;i<=m;++i) for(j=1;j<=n;++j) { hua[i][j+m]=fee[w][j][i]; hua[j+m][i]=-hua[i][j+m]; flow[i][j+m]=gy[i][w]; } for(i=1;i<=n;i++) flow[i+m][t]=xuqiu[i][w]; memset(pre,0,sizeof(int)*(n+m+2)); memset(vis,0,sizeof(int)*(n+m+2)); } int manzu() { int i,j,x,g; for(i=1;i<=k;++i) { x=g=0; for(j=1;j<=n;++j) x+=xuqiu[j][i]; for(j=1;j<=m;++j) g+=gy[j][i]; if(g<x) return 0; } return 1; } void chu() { int i; flow=new int*[n+m+2]; hua=new int*[n+m+2]; for(i=0;i<n+m+2;++i) { flow[i]=new int[n+m+2]; hua[i]=new int[n+m+2]; } pre=new int[n+m+2]; vis=new int[m+n+2]; dist=new int[n+m+2]; } ~solve() { int i,j; delete[] pre; delete[] vis; delete[] dist; for(i=0;i<n+m+2;++i) { delete[] flow[i]; delete[] hua[i]; } delete[] flow; delete[] hua; for(j=1;j<=n;++j) delete[] xuqiu[j]; for(j=1;j<=m;++j) delete[] gy[j]; delete[] xuqiu; delete[] gy; for(i=1;i<=k;++i) { for(j=1;j<=n;++j) delete[] fee[i][j]; delete[] fee[i]; } delete[] fee; } }; int main() { int n,m,k; while(cin>>n>>m>>k,n+m+k) solve poj2516(n,m,k); return 0; }