题意：给n,m,k表示商店数，储存店数，种类数
然后给n*k表示每个水果店需求每种种类的数量： 表示成 need[i][j]
再给m*k表示每个储存店每种种类数量: 表示成store[i][j]
再给k个 n*m的矩阵，表示第k种水果从j储物店运送到i商店的单位价格 cost[p][i][j]
思路：一下把图建完是不可能的，就是跑k次费用流，分别以每一种水果独立的跑，每次跑完后的最大流与该种水果所有的水果店希求总和如果相等，再跑下一种类的水果是否成立，不然就输出-1；
对于每一种水果的建图方法:---（f/cost）--- f表示流，cost表示费用
现在假设对第一种水果建图如下：
S(源点)----inff/0--->储物店---store[i][1]/0--->储物店---inff/cost[1][i][j]--->水果店----need[i][1]/0--->汇点
限流的地方有：将储物店拆点，以及水果店到汇点的流量最大为水果店的需求
费用体现的地方：储物店 与 水果店之间所建立的边。
具体代码：
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #include<set> #include<stack> #include<vector> #include<map> #include<queue> #define myself i,l,r #define lson i<<1 #define rson i<<1|1 #define Lson i<<1,l,mid #define Rson i<<1|1,mid+1,r #define half (l+r)/2 #define inff 0x3f3f3f3f #define lowbit(x) x&(-x) #define PI 3.14159265358979323846 #define min4(a,b,c,d) min(min(a,b),min(c,d)) #define min3(x,y,z) min(min(x,y),min(y,z)) #define pii make_pair #define pr pair<int,int> const int dir[4][2]={0,1,0,-1,1,0,-1,0}; typedef long long ll; const ll inFF=9223372036854775807; typedef unsigned long long ull; using namespace std; const int maxn=305; const int maxm=2e5+5; int pre[maxn],dis[maxn],vis[maxn],flow[maxn]; int need[55][55],store[55][55],cost[55][55][55]; int head[maxn],sign; int n,m,k,st,ed,mincost,maxflow; struct node { int to,p,f,d; }edge[maxm]; void init() { sign=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int f,int val) { edge[sign]=node{v,head[u],f,val}; head[u]=sign++; } void add_edge(int u,int v,int f,int val) { //cout<<u<<" "<<v<<" "<<f<<" "<<val<<endl; add(u,v,f,val); add(v,u,0,-val); } bool spfa() { for(int i=st;i<=ed;i++) { pre[i]=-1; vis[i]=0; flow[i]=dis[i]=inff; } vis[st]=1,dis[st]=0; queue<int> q; q.push(st); while(!q.empty()) { int u=q.front(); q.pop(),vis[u]=0; for(int i=head[u];~i;i=edge[i].p) { int v=edge[i].to,f=edge[i].f,d=edge[i].d; if(f>0&&dis[v]>dis[u]+d) { dis[v]=dis[u]+d; pre[v]=i; flow[v]=min(flow[u],f); if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[ed]!=inff; } void MCMF() { while(spfa()) { int f=flow[ed]; maxflow+=f;///最大流 mincost+=dis[ed]*f;///最小费用 for(int i=pre[ed];~i;i=pre[edge[i^1].to]) { edge[i].f-=f; edge[i^1].f+=f; } } } int main() { while(cin>>n>>m>>k,n+m+k) { st=0,ed=2*m+n+1; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) scanf("%d",&need[i][j]); for(int i=1;i<=m;i++) for(int j=1;j<=k;j++) scanf("%d",&store[i][j]); for(int p=1;p<=k;p++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&cost[p][i][j]); int ans=0; for(int p=1;p<=k;p++)//以每一种来跑费用流 { init(); int sum=mincost=maxflow=0; for(int i=1;i<=m;i++)//源点到储物店，储物点拆点限流 add_edge(0,i,inff,0),add_edge(i,i+m,store[i][p],0); for(int i=1;i<=n;i++) { sum+=need[i][p];//该种水果的需求 add_edge(2*m+i,ed,need[i][p],0);//水果店到汇点 } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) add_edge(j+m,2*m+i,inff,cost[p][i][j]);//储物店到水果店之间的费用 MCMF();//跑最小费用最大流 if(maxflow!=sum) {ans=-1;break;}//最大流不等于这种水果的需求 else ans+=mincost; } cout<<ans<<endl; } return 0; }
