题目链接：https://vjudge.net/problem/POJ-2516
思路：对于每种商品跑最小费用最大流，如果所有商品和人一起建图跑，O（v^2*m）数量级太大，会超时。
把店里的商品拆点，入和出之间是商品库存量，起到限流作用。
源点->人对该商品的需求->库存点入->库存点出->汇点
源点与人之间的边的流为人的需求量，人对商品之间的边的流INF。
源点与人的边设置费用，其他边费用0.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std; const int N = ,INF = (int)1e9;
int n,m,k,tot;
int head[N<<],pre[N<<],d[N<<],vis[N<<];
int p[N][N],g[N][N],c[N][N][N];
struct node{
int to,nxt,cap,flow,cost;
}e[N*N]; inline void add(int u,int v,int cap,int flow,int cost){
e[tot].to = v; e[tot].cap = cap; e[tot].flow = flow;
e[tot].cost = cost; e[tot].nxt = head[u]; head[u] = tot++; e[tot].to = u; e[tot].cap = ; e[tot].flow = flow;
e[tot].cost = -cost; e[tot].nxt = head[v]; head[v] = tot++;
} void input(int& sum_need){
sum_need = ;
for(int i = ; i <= n; ++i){
for(int j = ; j <= k; ++j){
scanf("%d",&p[i][j]);
sum_need += p[i][j];
}
}
for(int i = ; i <= m; ++i){
for(int j = ; j <= k; ++j)
scanf("%d",&g[i][j]);
}
for(int o = ; o <= k; ++o){
for(int i = ; i <= n; ++i){
for(int j = ; j <= m; ++j)
scanf("%d",&c[o][i][j]);
}
}
} void build_map(int o,int s,int t){
//0源点 1~n人 n+1~n+m 库存点入，
//n+m+1~n+2*m库存点出 n+2*m+1汇点。
for(int i = ; i <= n; ++i){
for(int j = ; j <= m; ++j){
add(i,j+n,INF,,c[o][i][j]);
}
}
for(int i = ; i <= n; ++i){
add(s,i,p[i][o],,);
}
for(int i = ; i <= m; ++i){
add(i+n,i+n+m,g[i][o],,);
add(i+n+m,t,INF,,);
}
} bool spfa(int s,int t){
for(int i = s; i <= t; ++i){
d[i] = INF; pre[i] = -; vis[i] = false;
}
queue<int > que;
que.push(s); d[s] = ; vis[s] = true;
while(!que.empty()){
int now = que.front(); que.pop();
vis[now] = false;
for(int o = head[now]; ~o; o = e[o].nxt){
int to = e[o].to;
if(e[o].cap > e[o].flow && d[to] > d[now] + e[o].cost){
d[to] = d[now] + e[o].cost;
pre[to] = o;
if(!vis[to]){
vis[to] = true;
que.push(to);
}
}
}
}
if(pre[t] == -) return false;
else return true;
} int mcmf(int s,int t,int& mf){ int Min = INF,mc = ;
while(spfa(s,t)){
Min = INF;
for(int o = pre[t]; ~o; o = pre[e[o^].to]){
Min = min(Min,e[o].cap - e[o].flow);
}
for(int o = pre[t]; ~o; o = pre[e[o^].to]){
e[o].flow += Min;
e[o^].flow -= Min;
}
mf += Min;
mc += d[t]*Min;
}
return mc;
} void init_main(){
memset(p,,sizeof(p));
memset(g,,sizeof(g));
memset(c,,sizeof(c));
} int main(){ int s,t,mc,mf,sum_need;//商品总需求量
while(~scanf("%d%d%d",&n,&m,&k) && (n+m+k)){
init_main();
input(sum_need);
s = ; t = n + *m + ;
mc = mf = ;
for(int o = ; o <= k; ++o){//第o种商品
for(int i = s; i <= t; ++i) head[i] = -; tot = ;
build_map(o,s,t);
mc += mcmf(s,t,mf);
}
//if(mf == sum_need) printf("-------------%d\n",mc);
//else printf("--------------no\n");
if(mf == sum_need) printf("%d\n",mc);
else printf("-1\n");
} return ;
}