/***************************************************************\* Author: Hu Wenbiao* Created Time: Sat 02 Oct 2010 08:31:09 PM CST* File Name: main.cpp* Description: 最小费用最大流。对每种货物用一次mcmf。\***************************************************************///*========================*Head File*========================*\\#include#include #include #include #include /*----------------------*Global Variable*----------------------*/#define maxn 105#define inf 0x3f3f3f3fstruct edge { int v, w, f, c, next;} e[5100];int vst[maxn], dis[maxn], start[maxn], p[maxn];int tot, N, M, K, flow_sum, ans, need[60][60], supply[60][60], cost, good_sum;//*=======================*Main Program*=======================*//using namespace std;void _add(int v, int w, int f, int c){ e[tot].v = v; e[tot].w = w; e[tot].f = f; e[tot].c = c; e[tot].next = start[v]; start[v] = tot++;}void add(int v, int w, int f, int c){ _add(v, w, f, c); _add(w, v, 0, -c);}bool spfa(int s, int t, int n){ int v, w; queue < int >q; for (int i = 0; i < n; i++) { p[i] = -1;; vst[i] = 0; dis[i] = inf; } vst[s] = 1; dis[s] = 0; q.push(s); while (!q.empty()) { v = q.front(); q.pop(); vst[v] = false; for (int i = start[v]; i != -1; i = e[i].next) { if (e[i].f) { w = e[i].w; if (dis[w] > dis[v] + e[i].c) { dis[w] = dis[v] + e[i].c; p[w] = i; if (!vst[w]) { vst[w] = true; q.push(w); } } } } } return dis[t] != inf;}int mcmf(int s, int t, int n){ int ans = 0, flow = inf, i; while (spfa(s, t, n)) { for (i = p[t]; i != -1; i = p[e[i].v]) if (e[i].f < flow) flow = e[i].f; for (i = p[t]; i != -1; i = p[e[i].v]) { e[i].f -= flow; e[i ^ 1].f += flow; } ans += dis[t] * flow; flow_sum += flow; } return ans;}int main(){//freopen("input","r",stdin); while (scanf("%d%d%d", &N, &M, &K) == 3 && N && M && K) { ans = 0; 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", &supply[i][j]); } } bool flag = true; for (int k = 1; k <= K; k++) { //第k种货物 flow_sum = 0; tot = 0; memset(start, -1, sizeof(start)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { scanf("%d", &cost); if (flag) add(j, M + i, 10000000, cost); } } for (int i = 1; i <= M; i++) { if (flag) add(0, i, supply[i][k], 0); } for (int i = 1; i <= N; i++) { if (flag) add(M + i, M + N + 1, need[i][k], 0); } if (flag) { ans += mcmf(0, N + M + 1, N + M + 2); good_sum = 0; for (int t = 1; t <= N; t++) good_sum += need[t][k]; if (flow_sum < good_sum) //所能达到的最大流小于需要的 flag = false; } } if (flag) printf("%d\n", ans); else printf("-1\n"); }}