思路与算法

每条网格边或外接边只有两端异色时才付代价，因此目标是将指定黑点与指定白点分开的最小割。一般最大流虽能建模，但本题需利用所有外接点位于平面网格外边界、总询问端点数不超过50的条件。

把内部每个小方格视作一个对偶点，跨过相邻方格的原网格边变为同权对偶边。按p从小到大排序本次外接点，外侧被这些射线分成k个扇区，对应k个额外对偶点。原边界网格边连向所属扇区，外接边本身变成其两侧扇区之间的同权对偶边。矩形四个角各有两条不同编号的射线，必须按原题顺时针编号分别处理。

相邻外接点的颜色不同时，把它们之间的扇区标为奇点；颜色相同时不标。目标是对偶图上恰好这些奇点具有奇度的最小边集合（最小T-join）。奇点个数d为偶数，且d≤k≤50。先从每个奇点跑Dijkstra得到奇点间最短距离，代码用非负整数键的radix heap。全部外接边形成一圈，总权W≤5×10^7，因此任意两个扇区沿圈取短方向的距离≤floor(W/2)，可据此剪去不可能改善距离的松弛。

在圆周顺序上总存在最优非交叉配对。以dp[l][r]表示连续偶数个奇点l..r的最小配对代价，枚举l与j配对，其中j-l为奇数，转移为dist[l][j]+dp[l+1][j-1]+dp[j+1][r]，空区间代价0。所有颜色相同或外接权总和0时直接输出0。相同询问可缓存。

正确性说明

对偶中的割边把外部给定颜色分区的边界表示出来。每个内部小方格绕行一周，颜色改变次数为偶数；每个外侧扇区沿边界绕行，其两端给定颜色异同决定改变次数的奇偶。因此割对应奇度点集合恰为颜色变化扇区的对偶边集合。反向沿这些对偶边翻转颜色，在平面中因内部奇偶条件而自洽，并满足外部指定颜色；两者总代价相同，所以最小割等于最小T-join。

非负权下，任意T-join可去掉无必要环并分解成奇点两两之间的路径；每条路径换成最短路不会增价。反之任意配对的最短路径取对称差，得到合法T-join且代价不超过各路长度之和。因此最小T-join等于奇点最短距离完全图上的最小权完美匹配。

奇点都在同一外面上。若两对的端点在圆周上交错，两条对应平面路径必相交；在交点交换路径尾部，得到两种不交错配对之一，总代价不增加，再缩短成最短路仍不增加。反复消去交错可得最优非交叉配对。对非交叉配对，l的配对点j将剩余点分成内外两个独立偶数区间，区间DP穷尽且只组合这种合法分解，按长度归纳得到最优匹配及原问题最优代价。

Dijkstra只在非负权上运行。外接边环给出每对扇区距离≤W/2的显式路径上界，故距离剪枝不会去掉必需的最短路。

复杂度

设V=(n-1)(m-1)+k，E=O(nm+k)，d≤k。初始读图与构造内部对偶边O(nm)时间、空间。每个询问恢复邻接表O(nm)，至多d-1次Dijkstra；radix heap对整数距离的摊还界可写为O(E log(U+1))每次，U≤25000000，随后区间DP O(d³)时间及O(d²)空间。总时间O(nm+Σ[k·(nm+k)log(U+1)+k³])，Σk≤50；每次距离初始化和清空堆已包含。图、距离、堆与区间矩阵空间O(nm+k²)，重复询问缓存所用键总长度不超过50。

易错点

输入先给纵向网格边，再给横向边，不能颠倒。p编号覆盖四个角的双射线，同一网格角点可以挂两个不同颜色端点；不能按网格顶点去重。每次询问的外侧扇区划分不同，要恢复内部对偶图再加本次边界边。颜色变化要包含末点与首点。只枚举奇数跨度j-l，保证两侧剩余区间长度均为偶数。零权边合法，不能当不存在。虽然原题能用最小割解释，最终程序采用对偶最短路与区间配对，非Dinic。数据是自编训练数据与公开样例，满规模点另有互不重叠路径和同值割的独立证书。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to, next, w;
};
struct Boundary {
    int face, gap, w;
};
struct RadixHeap {
    vector<pair<unsigned, int>> b[33];
    unsigned last = 0;
    size_t count = 0;
    static int bucket(unsigned x) {
        return x ? 32 - __builtin_clz(x) : 0;
    }
    void push(unsigned key, int value) {
        b[bucket(key ^ last)].push_back({key, value});
        ++count;
    }
    pair<unsigned, int> pop() {
        if (b[0].empty()) {
            int i = 1;
            while (b[i].empty())
                ++i;
            unsigned next = UINT_MAX;
            for (auto x : b[i])
                next = min(next, x.first);
            last = next;
            for (auto x : b[i])
                b[bucket(x.first ^ last)].push_back(x);
            b[i].clear();
        }
        auto x = b[0].back();
        b[0].pop_back();
        --count;
        return x;
    }
    bool empty() const {
        return count == 0;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, T;
    cin >> n >> m >> T;
    const int F = (n - 1) * (m - 1), INF = 1000000000;
    vector<int> head(F, -1);
    vector<Edge> edges;
    vector<Boundary> boundary;
    edges.reserve(2 * ((n - 1) * m + n * (m - 1) + 50));
    auto face = [&](int r, int c) {
        return r * (m - 1) + c;
    };
    auto add = [&](int u, int v, int w) {
        edges.push_back({v, head[u], w});
        head[u] = edges.size() - 1;
        edges.push_back({u, head[v], w});
        head[v] = edges.size() - 1;
    };
    for (int r = 0; r < n - 1; r++)
        for (int c = 0, w; c < m; c++) {
            cin >> w;
            if (c == 0)
                boundary.push_back({face(r, 0), 2 * (n + m) - r - 1, w});
            else if (c == m - 1)
                boundary.push_back({face(r, m - 2), m + r + 1, w});
            else
                add(face(r, c - 1), face(r, c), w);
        }
    for (int r = 0; r < n; r++)
        for (int c = 0, w; c < m - 1; c++) {
            cin >> w;
            if (r == 0)
                boundary.push_back({face(0, c), c + 1, w});
            else if (r == n - 1)
                boundary.push_back({face(n - 2, c), 2 * m + n - c - 1, w});
            else
                add(face(r - 1, c), face(r, c), w);
        }
    const vector<int> baseHead = head;
    const size_t baseEdges = edges.size();
    map<vector<array<int, 3>>, int> cache;
    while (T--) {
        int k;
        cin >> k;
        vector<array<int, 3>> q(k);
        for (auto &x : q)
            cin >> x[1] >> x[0] >> x[2];
        sort(q.begin(), q.end());
        auto cached = cache.find(q);
        if (cached != cache.end()) {
            cout << cached->second << '\n';
            continue;
        }
        vector<int> odd, ps(k);
        int total = 0;
        for (int i = 0; i < k; i++) {
            ps[i] = q[i][0];
            total += q[i][1];
            if (q[i][2] != q[(i + 1) % k][2])
                odd.push_back(i);
        }
        if (odd.empty() || total == 0) {
            cache[q] = 0;
            cout << 0 << '\n';
            continue;
        }
        head = baseHead;
        head.resize(F + k, -1);
        edges.resize(baseEdges);
        auto arc = [&](int gap) {
            int i = upper_bound(ps.begin(), ps.end(), gap) - ps.begin() - 1;
            return i < 0 ? k - 1 : i;
        };
        for (auto x : boundary)
            add(x.face, F + arc(x.gap), x.w);
        for (int i = 0; i < k; i++)
            add(F + (i + k - 1) % k, F + i, q[i][1]);
        int d = odd.size(), N = F + k, cap = total / 2;
        vector<int> oddIndex(k, -1);
        for (int i = 0; i < d; i++)
            oddIndex[odd[i]] = i;
        vector<vector<int>> distance(d, vector<int>(d, INF));
        for (int i = 0; i + 1 < d; i++) {
            vector<int> dist(N, INF);
            RadixHeap heap;
            dist[F + odd[i]] = 0;
            heap.push(0, F + odd[i]);
            int remaining = (d - i) / 2;
            while (!heap.empty()) {
                auto top = heap.pop();
                int now = top.first, u = top.second;
                if (now != dist[u])
                    continue;
                if (u >= F) {
                    int j = oddIndex[u - F];
                    if (j > i && ((j - i) & 1)) {
                        distance[i][j] = now;
                        if (--remaining == 0)
                            break;
                    }
                }
                for (int z = head[u]; z >= 0; z = edges[z].next) {
                    int v = edges[z].to, next = now + edges[z].w;
                    if (next <= cap && next < dist[v]) {
                        dist[v] = next;
                        heap.push(next, v);
                    }
                }
            }
            assert(remaining == 0);
        }
        vector<vector<int>> dp(d, vector<int>(d));
        for (int len = 2; len <= d; len += 2)
            for (int l = 0; l + len <= d; l++) {
                int r = l + len - 1, best = INF;
                for (int j = l + 1; j <= r; j += 2) {
                    int value = distance[l][j];
                    if (j > l + 1)
                        value += dp[l + 1][j - 1];
                    if (j < r)
                        value += dp[j + 1][r];
                    best = min(best, value);
                }
                dp[l][r] = best;
            }
        int answer = dp[0][d - 1];
        cache[q] = answer;
        cout << answer << '\n';
    }
}