[BJOI2018] Kakuro

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <limits>
#include <queue>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct Num {
    ll d, infs;

    Num(ll d = 0, ll infs = 0) : d(d), infs(infs) {}

    bool operator<(const Num& x) const {
        if (infs != x.infs)
            return infs < x.infs;
        return d < x.d;
    }

    Num operator+(const Num& x) const {
        return Num(d + x.d, infs + x.infs);
    }

    Num operator*(ll x) const {
        return Num(d * x, infs * x);
    }

    friend Num operator*(ll x, const Num& y) {
        return y * x;
    }

    Num& operator+=(const Num& x) {
        d += x.d;
        infs += x.infs;
        return *this;
    }
};

struct Edge {
    int v, w;
    Num c;
    Edge *next, *rev;
};

const int N = 32, V = N * N, T = V - 1, S = V - 2;
const Num INF = Num(0, 1);

int n, m, nCnt;
int typ[N][N];
int a[N][N][2];
int fromRow[N][N];
Num cst[N][N][2];

bool inq[V];
Edge* pth[V];
Num dist[V];

Edge* g[V];

Edge* addEdge(int u, int v, int w, const Num& c);
void link(int u, int v, int w, const Num& c);
Num mcf();
bool spth();

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &typ[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if ((typ[i][j] & 1) || typ[i][j] == 4)
                scanf("%d", &a[i][j][0]);
            if (typ[i][j] & 2)
                scanf("%d", &a[i][j][1]);
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int x;
            if ((typ[i][j] & 1) || typ[i][j] == 4) {
                scanf("%d", &x);
                if (x == -1)
                    cst[i][j][0] = INF;
                else
                    cst[i][j][0] = x;
            }
            if (typ[i][j] & 2) {
                scanf("%d", &x);
                if (x == -1)
                    cst[i][j][1] = INF;
                else
                    cst[i][j][1] = x;
            }
        }
    Num curCost = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (typ[i][j] & 2) {
                ++nCnt;
                int cnt = 0, orij = j;
                for (++j; typ[i][j] == 4; ++j) {
                    fromRow[i][j] = nCnt;
                    ++cnt;
                }
                int used = abs(a[i][orij][1] - cnt);
                curCost += used * cst[i][orij][1];
                if (a[i][orij][1] > cnt)
                    link(S, nCnt, used, cst[i][orij][1] * -1);
                link(S, nCnt, numeric_limits<int>::max(), cst[i][orij][1]);
                --j;
            }
        }
    for (int j = 1; j <= m; ++j)
        for (int i = 1; i <= n; ++i)
            if (typ[i][j] & 1) {
                ++nCnt;
                int cnt = 0, orii = i;
                for (++i; typ[i][j] == 4; ++i) {
                    int used = abs(a[i][j][0] - 1);
                    curCost += used * cst[i][j][0];
                    ++cnt;
                    link(fromRow[i][j], nCnt, used, cst[i][j][0] * -1);
                    link(fromRow[i][j], nCnt, numeric_limits<int>::max(), cst[i][j][0]);
                }
                int used = abs(a[orii][j][0] - cnt);
                curCost += used * cst[orii][j][0];
                if (a[orii][j][0] > cnt)
                    link(nCnt, T, used, cst[orii][j][0] * -1);
                link(nCnt, T, numeric_limits<int>::max(), cst[orii][j][0]);
                --i;
            }
    LOG("%lld %lld\n", curCost.d, curCost.infs);
    curCost += mcf();
    LOG("%lld %lld\n", curCost.d, curCost.infs);
    if (curCost.infs)
        puts("-1");
    else
        printf("%lld\n", curCost.d);
    return 0;
}

Num mcf() {
    Num cost = 0;
    while (spth()) {
        LOG("%lld %lld\n", dist[T].d, dist[T].infs);
        if (!(dist[T] < 0))
            break;
        int flow = numeric_limits<int>::max();
        int u = T;
        while (u != S) {
            flow = min(flow, pth[u]->rev->w);
            u = pth[u]->v;
        }
        cost += dist[T] * flow;
        u = T;
        while (u != S) {
            pth[u]->w += flow;
            pth[u]->rev->w -= flow;
            u = pth[u]->v;
        }
    }
    return cost;
}

bool spth() {
    queue<int> q;
    memset(pth, 0, sizeof(pth));
    memset(inq, 0, sizeof(inq));
    inq[S] = true;
    dist[S] = 0;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        LOG("BFS %d %lld %lld\n", u, dist[u].d, dist[u].infs);
        inq[u] = false;
        for (Edge* p = g[u]; p; p = p->next)
            if (p->w && p->v != S && (!pth[p->v] || dist[u] + p->c < dist[p->v])) {
                dist[p->v] = dist[u] + p->c;
                pth[p->v] = p->rev;
                if (!inq[p->v]) {
                    q.push(p->v);
                    inq[p->v] = true;
                }
            }
    }
    return pth[T];
}

void link(int u, int v, int w, const Num& c) {
    LOG("LINK %d %d %d %lld + %lldINF\n", u, v, w, c.d, c.infs);
    Edge *p = addEdge(u, v, w, c),
            *q = addEdge(v, u, 0, c * -1);
    p->rev = q;
    q->rev = p;
}

Edge* addEdge(int u, int v, int w, const Num& c) {
    static Edge pool[V * V * 4];
    static Edge* p = pool;
    p->v = v;
    p->w = w;
    p->c = c;
    p->next = g[u];
    g[u] = p;
    return p++;
}