POJ2516.md

K个商品是独立的，所以跑k次费用流即可

#include<cstring>
#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 222;
const int INF = 0x3f3f3f3f;
#define S 0
#define T MAXN - 1
int n,m,k,dist[MAXN][MAXN][MAXN],A[MAXN][MAXN],B[MAXN][MAXN],flow[MAXN],pre[MAXN],pid[MAXN],vis[MAXN],c[MAXN];
struct EDGE{
    int to, cap, fee, rev;
    EDGE(){}
    EDGE(int _to,int _cap, int _fee, int _rev){to = _to; cap = _cap; fee =_fee; rev = _rev;}
};
vector<EDGE> G[MAXN];
void ADDEDGE(int u, int v, int cap, int fee){
    G[u].push_back(EDGE(v,cap,fee,(int)G[v].size()));
    G[v].push_back(EDGE(u,0,-fee,(int)G[u].size()-1));
}
bool spfa(){
    memset(vis,0,sizeof(vis));
    memset(c,INF,sizeof(c));
    c[S] = 0;
    pre[T] = -1;
    flow[S] = INF;
    queue<int> que;
    que.push(S);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vis[u] = false;
        for(int i = 0; i < (int)G[u].size(); i++){
            EDGE &e = G[u][i];
            if(!e.cap || c[e.to] <= c[u] + e.fee) continue;
            c[e.to] = c[u] + e.fee;
            pre[e.to] = u;
            pid[e.to] = i;
            flow[e.to] = min(flow[u],e.cap);
            if(!vis[e.to]){
                vis[e.to] = true;
                que.push(e.to);
            }
        }
    }
    return pre[T] != -1;
}
int mcmf(int kk){
    for(int i = 0; i < MAXN; i++) G[i].clear();
    int nd = 0, hv = 0;
    for(int i = 1; i <= m; i++){
        hv += B[i][kk];
        ADDEDGE(S,i,B[i][kk],0);
    }
    for(int i = 1; i <= n; i++){
        nd += A[i][kk];
        ADDEDGE(m+i,T,A[i][kk],0);
    }
    if(hv<nd) return -1;
    for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) ADDEDGE(i,j+m,INF,dist[kk][j][i]);
    int cost = 0;
    while(spfa()){
        cost += flow[T] * c[T];
        int rt = T;
        while(rt){
            G[pre[rt]][pid[rt]].cap -= flow[T];
            G[rt][G[pre[rt]][pid[rt]].rev].cap += flow[T];
            rt = pre[rt];
        }
    }
    return cost;
}
int solve(){
    int tot = 0;
    for(int kk = 1; kk <= k; kk++){
        int cst = mcmf(kk);
        if(cst==-1) return -1;
        else tot += cst;
    }
    return tot;
}
int main(){
    while(scanf("%d %d %d",&n,&m,&k)!=EOF&&n+m+k){
        for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) scanf("%d",&A[i][j]);
        for(int i = 1; i <= m; i++) for(int j = 1; j <= k; j++) scanf("%d",&B[i][j]);
        for(int kk = 1; kk <= k; kk++) for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d",&dist[kk][i][j]);
        printf("%d\n",solve());
    }
    return 0;
}