题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#pragma GCC optimize(2,"Ofast,inline,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=(l),num##i=(r);i<=num##i;++i)
#define per(i,r,l) for(int i=(r),num##i=(l);i>=num##i;--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fileI(x) freopen(x,"r",stdin)
#define fileO(x) freopen(x,"w",stdout)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e3 + 5, INF = 0x3f3f3f3f;
const int dir[4][4] = {
    {0, 1, 2, 3},
    {1, 2, 3, 0},
    {2, 3, 0, 1},
    {3, 0, 1, 2}
};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m;

const int V = N * 4, M = N * 15;
struct Flow {
    struct Edge {
        int to, nxt, w, c;
    } e[M << 1];
    int head[V], elen;
    void Insert(int u, int v, int w, int c) {
        e[++elen] = (Edge) {
            v, head[u], w, c
        };
        head[u] = elen;
    }
    void addedge(int u, int v, int w, int c) {
        Insert(u, v, w, c), Insert(v, u, 0, -c);
    }

    int n, m, s, t;

    int h[V], dis[V];
    int flow[V], pre[V];
    bool vis[V];
    queue<int> que;

    Flow() {
        elen = 1;
    }
    void Spfa() {
        rep(i, 0, t) h[i] = INF;
        h[s] = 0, vis[s] = 1;
        que.push(s);

        while (!que.empty()) {
            int u = que.front();
            que.pop();
            vis[u] = 0;

            for (int i = head[u], v; i; i = e[i].nxt) {
                v = e[i].to;

                if (e[i].w > 0 && h[v] > h[u] + e[i].c) {
                    h[v] = h[u] + e[i].c;

                    if (!vis[v])
                        vis[v] = 1, que.push(v);
                }
            }
        }
    }
    priority_queue<pii, vector<pii >, greater<pii >> que2;
    bool Dij() {
        rep(i, 0, t) dis[i] = INF, vis[i] = 0;
        dis[s] = 0, flow[s] = INF;
        que2.push({0, s});

        while (!que2.empty()) {
            int u = que2.top().se;
            que2.pop();

            if (vis[u])
                continue;

            vis[u] = 1;

            for (int i = head[u], v, nc; i; i = e[i].nxt) {
                v = e[i].to;
                nc = e[i].c + h[u] - h[v];

                if (e[i].w > 0 && dis[v] > dis[u] + nc) {
                    dis[v] = dis[u] + nc;
                    flow[v] = min(flow[u], e[i].w);
                    pre[v] = i;
                    que2.push({dis[v], v});
                }
            }
        }

        return vis[t];
    }
    pii EK() {
        int maxflow = 0, mincost = 0;

        while (Dij()) {
            rep(i, 0, t)h[i] += dis[i];
            int v = t, ft = flow[t];
            maxflow += ft;
            mincost += h[t] * ft;

            while (v != s) {
                e[pre[v]].w -= ft;
                e[pre[v] ^ 1].w += ft;
                v = e[pre[v] ^ 1].to;
            }
        }

        return {maxflow, mincost};
    }
} F;

// 0 1 2 3: 上右左下
int ID(int x, int y, int d) {
    return ((x - 1) * m + y - 1) * 4 + d + 1;
}

#define E(u,v,w,c) F.addedge(u,v,w,c)

int goal;

void Link1(int x, int y, const int d[4]) {
    if (!(x + y & 1)) {
        E(ID(x, y, d[0]), ID(x, y, d[1]), 1, 1);
        E(ID(x, y, d[0]), ID(x, y, d[3]), 1, 1);
        E(ID(x, y, d[0]), ID(x, y, d[2]), 1, 2);
    } else {
        E(ID(x, y, d[1]), ID(x, y, d[0]), 1, 1);
        E(ID(x, y, d[3]), ID(x, y, d[0]), 1, 1);
        E(ID(x, y, d[2]), ID(x, y, d[0]), 1, 2);
    }
}
void Link2(int x, int y, const int d[4]) {
    if (!(x + y & 1)) {
        E(ID(x, y, d[0]), ID(x, y, d[2]), 1, 1);
        E(ID(x, y, d[1]), ID(x, y, d[3]), 1, 1);
    } else {
        E(ID(x, y, d[2]), ID(x, y, d[0]), 1, 1);
        E(ID(x, y, d[3]), ID(x, y, d[1]), 1, 1);
    }
}
void Link3(int x, int y, const int d[4]) {
    if (!(x + y & 1)) {
        E(ID(x, y, d[1]), ID(x, y, d[0]), 1, 1);
        E(ID(x, y, d[3]), ID(x, y, d[0]), 1, 1);
        E(ID(x, y, d[2]), ID(x, y, d[0]), 1, 2);
    } else {
        E(ID(x, y, d[0]), ID(x, y, d[1]), 1, 1);
        E(ID(x, y, d[0]), ID(x, y, d[3]), 1, 1);
        E(ID(x, y, d[0]), ID(x, y, d[2]), 1, 2);
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int s = F.s = 0, t = F.t = n * m * 4 + 1;
    rep(x, 1, n)rep(y, 1, m) {
        if (x + y & 1) {
            rep(i, 0, 3) {
                int nx = x + dx[i], ny = y + dy[i];

                if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
                    E(ID(nx, ny, i ^ 2), ID(x, y, i), 1, 0);
                }
            }
        }

        int S;
        cin >> S;

        if (!S)
            continue;

        int tot = __builtin_popcount(S);
        goal += tot;

        if (!(x + y & 1)) {

            rep(i, 0, 3)if (S >> i & 1) {
                E(s, ID(x, y, i), 1, 0);
            }
        } else {

            rep(i, 0, 3)if (S >> i & 1) {
                E(ID(x, y, i), t, 1, 0);
            }
        }

        if (tot == 1) {
            Link1(x, y, dir[__lg(S)]);
        } else if (tot == 2) {
            if (S == 0b1001 || S & S << 1) {
                Link2(x, y, dir[S == 0b1001 ? 3 : __builtin_ctz(S)]);
            }
        } else if (tot == 3) {
            Link3(x, y, dir[__lg(S ^ 0b1111)]);
        }
    }
    F.Spfa();
    pii ans = F.EK();

    if (ans.fi * 2 != goal)
        cout << "-1";
    else
        cout << ans.se;

    return 0;
}