View Code
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; #define maxn 110 #define maxm 6000 #define inf 1000000000 int min(int a, int b) { return a < b ? a : b; } struct E { int u, v, next, c, w; }edge[maxm<<2]; int head[maxn], tot; int n, m, k; int S, T; int sum[55]; void add(int s, int t, int c, int w) { edge[tot].u = s; edge[tot].v = t; edge[tot].c = c; edge[tot].w = w; edge[tot].next = head[s]; head[s] = tot++; edge[tot].u = t; edge[tot].v = s; edge[tot].c = 0; edge[tot].w = -w; edge[tot].next = head[t]; head[t] = tot++; } void init() { tot = 0; memset(head, -1, sizeof(head)); } int pre[maxn]; int dis[maxn]; bool vis[maxn]; bool spfa(int s, int t, int n) { int i, u, v; for(i = 0; i <= n; i++) dis[i] = inf, pre[i] = -1, vis[i] = 0; queue<int> q; vis[s] = 1; dis[s] = 0; q.push(s); while(!q.empty()) { u = q.front(); q.pop(); vis[u] = 0; for(i = head[u]; i != -1; i = edge[i].next) { v = edge[i].v; if(edge[i].c && dis[v] > dis[u] + edge[i].w) { dis[v] = dis[u] + edge[i].w; pre[v] = i; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } if(dis[t] == inf) return 0; return 1; } int ans, maxf; int mfmw(int s, int t, int n) { int aug, minw = 0, i; maxf = 0; while(spfa(s, t, n)) { aug = inf + 1; for(i = pre[t]; i != -1; i = pre[edge[i].u]) aug = min(aug, edge[i].c); for(i = pre[t] ;i != -1; i = pre[edge[i].u]) { edge[i].c -= aug; edge[i^1].c += aug; } maxf += aug; minw += dis[t] * aug; } return minw; } char map[55][55][55], a[55][55], b[55][55]; int main() { int i, j, u; int x, y, z; while( ~scanf("%d%d%d", &n, &m, &k)) { if(!m && !n && !k) break; maxf = ans = 0; memset(sum, 0, sizeof(sum)); for(i = 1; i <= n; i++) for(j = 1; j <= k; j++) scanf("%d", &a[i][j]), sum[j] += a[i][j]; for(i = 1; i <= m; i++) for(j = 1; j <= k; j++) scanf("%d", &b[i][j]); S = 0; T = n+m+1; bool flag = 1; for(u = 1; u <= k; u++) { init(); for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) { scanf("%d", &z); add(j+n, i, inf, z); } if(!flag) continue; for(i = 1; i <= m; i++) add(S, i+n, b[i][u], 0); for(i = 1; i <= n; i++) add(i, T, a[i][u], 0); int pp = mfmw(S, T, T+1); if(maxf != sum[u]) flag = 0; ans += pp; } if(flag) printf("%d\n", ans); else puts("-1"); } return 0; }