1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
|
#include <climits> #include <queue> #include <algorithm> const int MAXN = 105; struct ; struct Node { Edge *e, *curr; int level; } N[MAXN * MAXN * 5]; struct { Node *u, *v; Edge *next, *rev; int cap, flow; Edge(Node *u, Node *v, int cap) : u(u), v(v), cap(cap), flow(0), next(u->e) {} }; void addEdge(int u, int v, int cap) { N[u].e = new Edge(&N[u], &N[v], cap); N[v].e = new Edge(&N[v], &N[u], 0); N[u].e->rev = N[v].e; N[v].e->rev = N[u].e; } struct Dinic { bool makeLevelGraph(Node *s, Node *t, int n) { for (int i = 0; i < n; i++) N[i].level = 0; std::queue<Node *> q; q.push(s); s->level = 1; while (!q.empty()) { Node *u = q.front(); q.pop(); for (Edge *e = u->e; e; e = e->next) { if (e->cap > e->flow && e->v->level == 0) { e->v->level = u->level + 1; if (e->v == t) return true; q.push(e->v); } } } return false; } int findPath(Node *s, Node *t, int limit = INT_MAX) { if (s == t) return limit; for (Edge *&e = s->curr; e; e = e->next) { if (e->cap > e->flow && e->v->level == s->level + 1) { int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow)); if (flow > 0) { e->flow += flow; e->rev->flow -= flow; return flow; } } } return 0; } int operator()(int s, int t, int n) { int res = 0; while (makeLevelGraph(&N[s], &N[t], n)) { for (int i = 0; i < n; i++) N[i].curr = N[i].e; int flow; while ((flow = findPath(&N[s], &N[t])) > 0) res += flow; } return res; } } dinic; int main() { int n, m; scanf("%d %d", &n, &m); int sum = 0; static int a[MAXN][MAXN], b[MAXN][MAXN], aR[MAXN][MAXN], bR[MAXN][MAXN], aC[MAXN][MAXN], bC[MAXN][MAXN]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]), sum += a[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &b[i][j]); for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) scanf("%d", &aR[i][j]), sum += aR[i][j]; for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) scanf("%d", &bR[i][j]); for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) scanf("%d", &aC[i][j]), sum += aC[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) scanf("%d", &bC[i][j]); int index = 0; static int id[MAXN][MAXN][5]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 0; k < 5; k++) id[i][j][k] = ++index; const int s = 0, t = n * m * 5 + 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int x = b[i][j] - a[i][j]; if (x > 0) addEdge(s, id[i][j][0], x), sum += x; else addEdge(id[i][j][0], t, -x); if (i != n) { addEdge(id[i][j][1], t, aR[i][j]); addEdge(s, id[i][j][2], bR[i][j]), sum += bR[i][j]; addEdge(id[i][j][2], id[i][j][0], INT_MAX); addEdge(id[i][j][2], id[i + 1][j][0], INT_MAX); addEdge(id[i][j][0], id[i][j][1], INT_MAX); addEdge(id[i + 1][j][0], id[i][j][1], INT_MAX); } if (j != m) { addEdge(id[i][j][3], t, aC[i][j]); addEdge(s, id[i][j][4], bC[i][j]), sum += bC[i][j]; addEdge(id[i][j][4], id[i][j][0], INT_MAX); addEdge(id[i][j][4], id[i][j + 1][0], INT_MAX); addEdge(id[i][j][0], id[i][j][3], INT_MAX); addEdge(id[i][j + 1][0], id[i][j][3], INT_MAX); } } printf("%dn", sum - dinic(s, t, t + 1)); return 0; }
|