112. 作业之地理篇 最小费用最大流模板题

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 30 * 30 * 4;
struct Edge {
    int u, v, w, cost, tonext;
}e[maxn * 2];
int first[maxn], num;
int n, m;
void addEdge(int u, int v, int w, int cost) {
    e[num].u = u, e[num].v = v, e[num].w = w, e[num].cost = cost, e[num].tonext = first[u];
    first[u] = num++;
}
int x[maxn], y[maxn], DFN;
int getID(int x, int y) {
    return (x - 1) * m + y;
}

int flow[maxn], pre[maxn];
int dis[maxn], tim[maxn];
bool in[maxn];
bool spfa(int bx, int n) {
    for (int i = 0; i <= n; ++i) {
        dis[i] = inf;
        tim[i] = 0;
        in[i] = false;
        flow[i] = 0;
    }
    queue<int> que;
    while (!que.empty()) que.pop();
    que.push(bx), in[bx] = true, dis[bx] = 0, tim[bx]++, flow[bx] = inf;
    pre[bx] = -inf;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = first[u]; ~i; i = e[i].tonext) {
            if (e[i].w > 0 && dis[e[i].v] > dis[e[i].u] + e[i].cost) { //²»Óñê¼Çflow
                dis[e[i].v] = dis[e[i].u] + e[i].cost;
                pre[e[i].v] = i;
                flow[e[i].v] = min(e[i].w, flow[u]);
                if (!in[e[i].v]) {
                    que.push(e[i].v);
                    in[e[i].v] = true;
                    tim[e[i].v]++;
                }
            }
        }
        in[u] = false;
    }
    if (flow[n] == 0) return false;
    else return true;
}
LL ans;
int maxFlow(int be, int en) {
    int sumFlow = 0;
    while (spfa(0, en)) {
//        cout << dis[en] << endl;
        ans += 1LL * dis[en] * flow[en];
        int res = flow[en];
        int edgeID = pre[en];
        while (edgeID != -inf) {
            e[edgeID].w -= res;
            e[edgeID ^ 1].w += res;
            edgeID = pre[e[edgeID].u];
        }
        sumFlow += res;
    }
    return sumFlow;
}

set< pair<int, int> > ss;

void work() {
    memset(first, -1, sizeof first);
    num = 0, ++DFN;
    ss.clear();
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i) {
        int xi, yi;
        scanf("%d%d", &xi, &yi);
        ss.insert(make_pair(xi, yi));
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m - 1; ++j) {
            int val;
            scanf("%d", &val);
            if (ss.count(make_pair(i, j)) || ss.count(make_pair(i, j + 1))) continue;
            addEdge(getID(i, j), getID(i, j + 1) + n * m, 1, val);
            addEdge(getID(i, j + 1) + n * m, getID(i, j), 0, -val);

            addEdge(getID(i, j + 1), getID(i, j) + n * m, 1, val);
            addEdge(getID(i, j) + n * m, getID(i, j + 1), 0, -val);
        }
    }
    for (int i = 1; i <= n - 1; ++i) {
        for (int j = 1; j <= m; ++j) {
            int val;
            scanf("%d", &val);
            if (ss.count(make_pair(i, j)) || ss.count(make_pair(i + 1, j))) continue;
            addEdge(getID(i, j), getID(i + 1, j) + n * m, 1, val);
            addEdge(getID(i + 1, j) + n * m, getID(i, j), 0, -val);

            addEdge(getID(i + 1, j), getID(i, j) + n * m, 1, val);
            addEdge(getID(i, j) + n * m, getID(i + 1, j), 0, -val);

        }
    }
    if ((n * m - q) & 1) {
        printf("-1
");
        return;
    }
    for (int i = 1; i <= n * m; ++i) {
        addEdge(0, i, 1, 0);
        addEdge(i, 0, 0, 0);
        addEdge(n * m + i, 2 * n * m + 1, 1, 0);
        addEdge(2 * n * m + 1, n * m + i, 0, 0);
    }
//    for (int i = first[5]; ~i; i = e[i].tonext) {
//        printf("%d %d %d %d
", e[i].u, e[i].v, e[i].w, e[i].cost);
//    }
    ans = 0;
    int res = maxFlow(0, 2 * n * m + 1);
//    cout << res << endl;
    if (res != (n * m - q)) {
        printf("-1
");
    } else printf("%lld
", ans / 2);
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    while (scanf("%d%d", &n, &m) > 0) work();
    return 0;
}