问题分析

本题是一个平面图最小割问题，需要将网格点黑白染色，使得异色边权值和最小。附加点相当于在网格外部增加了固定颜色的点，将问题转化为带约束的最小割问题。

核心思路

算法框架：环形DP + 最短路预处理

• 图模型建立：将网格转化为对偶图

• 射线处理：将附加点按环形顺序排列

• 最短路预处理：计算相邻异色附加点之间的最小割值

• 环形区间DP：求解环形结构上的最优匹配

关键数据结构

struct edge {
    int v, w, next;  // 邻接表存储图结构
} e[N * 10];

int h[N], h_[N], id;  // 图头指针和备份
int b[N], tot;        // 标记边界段编号
vector<int> point[105]; // 每个边界段包含的网格点
int g[105][105];      // 相邻异色点间最小割值
int f[105][105];      // DP数组

算法详解

1.图构建阶段

// 构建原始网格图
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= m; j++) {
        int w = read();
        // 水平边连接
        addedge(get(i, j - 1), get(i, j), w);
        addedge(get(i, j), get(i, j - 1), w);
    }
}

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < m; j++) {
        int w = read();
        // 垂直边连接  
        addedge(get(i - 1, j), get(i, j), w);
        addedge(get(i, j), get(i - 1, j), w);
    }
}

2.边界射线编号系统

// 将射线编号映射到网格边界点
int get_(int x) {
    if (x <= m) return get(0, x);           // 上边界
    if (x <= m + n) return get(x - m, m);   // 右边界
    if (x <= m + n + m) {                   // 下边界
        x -= (m + n);
        return get(n, m - x + 1);
    }
    x -= (m + n + m);                       // 左边界
    return get(n - x + 1, 0);
}

3.附加点处理与边界分段

// 处理附加点，将边界划分为若干段
for (int i = 1; i <= 2 * (n + m); i++) {
    if (c[i] == -1) continue;
    
    // 找到下一个异色附加点
    for (int j = i + 1;; j++) {
        if (j > 2 * (n + m)) j = 1;
        if (c[j] == -1) continue;
        
        if (c[i] != c[j]) {
            tot++;
            int x = get_(i), y = get_(j);
            // 标记两个异色点之间的边界段
            int flag = 0;
            for (auto u : out) {
                if (u == x) flag = 1;
                if (flag) {
                    if (u == y) break;
                    b[u] = tot;           // 标记边界点所属段
                    point[tot].push_back(u); // 记录段内点
                }
            }
        }
        break;
    }
}

4.最短路预处理

void dij(int s) {
    // 多源最短路，计算段s到其他段的最小割值
    for (auto u : point[s]) {
        dist[u] = 0;
        q.push({u, 0});
    }
    
    while (!q.empty()) {
        int u = q.top().u; q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        
        // 记录到达其他边界段的最小距离
        if (b[u] > 0 && g[s][b[u]] == -1) {
            g[s][b[u]] = dist[u];
        }
        
        for (int i = h[u]; ~i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({v, dist[v]});
            }
        }
    }
}

5.环形区间DP

for (int len = 2; len <= tot; len += 2) {
    for (int i = 1, j = i + len - 1; j <= tot; i++, j++) {
        f[i][j] = INF;
        // 枚举匹配点对
        for (int k = i + 1; k <= j; k += 2) {
            f[i][j] = min(f[i][j], 
                g[i][k] +        // i与k匹配的代价
                f[i + 1][k - 1] + // 中间区间最优解
                f[k + 1][j]);     // 右侧区间最优解
        }
    }
}

复杂度分析

时间复杂度

• 图构建：$O(nm)$

• 最短路预处理：$O(k \cdot nm \log(nm))$，其中 $k \leq 50$

• 环形DP：$O(k^3)$

总复杂度：在数据范围内可接受

空间复杂度

• $O(nm)$ 存储图结构

• $O(k^2)$ 存储DP数组

关键优化

环形边界处理：将网格外部视为环形结构

多源最短路：一次性计算整个边界段到其他段的最小割

区间DP：利用环形结构的最优子结构性质

图备份：避免重复构建图结构

样例分析

对于样例输入：

网格大小：$2 \times 3$

附加点：射线3（黑色）和射线9（白色）

通过计算得到最小割值为12

最优染色方案如题目所述

总结

本题通过巧妙的图论建模，将网格染色问题转化为环形结构上的最小割问题。算法结合了最短路和动态规划技术，充分利用了平面图和对偶图的性质。环形区间DP的处理方式是该解法的核心创新点，有效解决了环形约束下的最优匹配问题。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2.6e5;
struct edge {
    int v, w, next;
} e[N * 10];
int h[N], h_[N], id;
void addedge(int u, int v, int w) {
    e[id] = {v, w, h[u]};
    h[u] = id++;
}
int n, m, _;
int a[2005], c[2005];
int b[N], tot = 0;
int f[105][105], g[105][105];
int get(int x, int y) {
    return x * (m + 1) + y;
}
int get_(int x) {
    if (x <= m)
        return get(0, x);

    if (x <= m + n)
        return get(x - m, m);

    if (x <= m + n + m) {
        x -= (m + n);
        x = m - x + 1;
        return get(n, x - 1);
    }

    x -= (m + n + m);
    x = n - x + 1;
    return get(x - 1, 0);
}
vector<int>out, point[105];

struct node {
    int u, dis;
    bool operator <(const node &b)const {
        return dis > b.dis;
    }
};
int dist[N], vis[N];
void dij(int s) {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    priority_queue<node>q;

    for (auto u : point[s]) {
        dist[u] = 0;
        q.push({u, 0});
    }

    int cnt = 0;

    while (!q.empty() && cnt < tot) {
        int u = q.top().u;
        q.pop();

        if (vis[u])
            continue;

        vis[u] = 1;

        if (b[u] > 0 && g[s][b[u]] == -1) {
            g[s][b[u]] = dist[u];
            cnt++;
        }

        for (int i = h[u]; ~i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({v, dist[v]});
            }
        }
    }
}
int main() {
    //freopen("traffic.in", "r", stdin);
    //freopen("traffic.out", "w", stdout);
    memset(h, -1, sizeof(h));
    cin >> n >> m >> _;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            int w;
            cin >> w;
            addedge(get(i, j - 1), get(i, j), w);
            addedge(get(i, j), get(i, j - 1), w);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            int w;
            cin >> w;
            addedge(get(i - 1, j), get(i, j), w);
            addedge(get(i, j), get(i - 1, j), w);
        }
    }

    for (int j = 0; j <= 1; j++) {
        for (int i = 0; i <= m; i++)
            out.push_back(get(0, i));

        for (int i = 1; i <= n - 1; i++)
            out.push_back(get(i, m));

        for (int i = m; i >= 0; i--)
            out.push_back(get(n, i));

        for (int i = n - 1; i >= 1; i--)
            out.push_back(get(i, 0));
    }

    memcpy(h_, h, sizeof(h));

    while (_--) {
        memcpy(h, h_, sizeof(h));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, -1, sizeof(c));
        memset(g, -1, sizeof(g));

        for (int i = 1; i <= tot; i++)
            point[i].clear();

        tot = 0;
        int T, flag = 0;
        cin >> T;

        for (int i = 1; i <= T; i++) {
            int x, p, t;
            cin >> x >> p >> t;
            a[p] = x;
            c[p] = t;
            flag |= 1 << t;
        }

        if (flag != 3) {
            cout << 0 << endl;
            continue;
        }

        for (int i = 1; i <= m; i++) {
            addedge(get(0, i - 1), get(0, i), a[i]);
            addedge(get(0, i), get(0, i - 1), a[i]);
        }

        for (int i = 1; i <= n; i++) {
            addedge(get(i - 1, m), get(i, m), a[i + m]);
            addedge(get(i, m), get(i - 1, m), a[i + m]);
        }

        for (int i = 1; i <= m; i++) {
            addedge(get(n, m - i + 1), get(n, m - i), a[i + m + n]);
            addedge(get(n, m - i), get(n, m - i + 1), a[i + m + n]);
        }

        for (int i = 1; i <= n; i++) {
            addedge(get(n - i + 1, 0), get(n - i, 0), a[i + m + n + m]);
            addedge(get(n - i, 0), get(n - i + 1, 0), a[i + m + n + m]);
        }

        for (int i = 1; i <= 2 * (n + m); i++) {
            if (c[i] == -1)
                continue;

            for (int j = i + 1;; j++) {
                if (j > 2 * (n + m))
                    j = 1;

                if (c[j] == -1)
                    continue;

                if (c[i] != c[j]) {
                    tot++;
                    int x = get_(i), y = get_(j);
                    int flag = 0;

                    for (auto u : out) {
                        if (u == x)
                            flag = 1;

                        if (flag) {
                            if (u == y)
                                break;

                            b[u] = tot;
                            point[tot].push_back(u);
                        }
                    }
                }

                break;
            }
        }

        for (int i = 1; i <= tot; i++) {
            dij(i);
        }

        for (int len = 2; len <= tot; len += 2) {
            for (int i = 1, j = i + len - 1; j <= tot; i++, j++) {
                f[i][j] = 0x3f3f3f3f;

                for (int k = i + 1; k <= j; k += 2) {
                    f[i][j] = min(f[i][j], g[i][k] + f[i + 1][k - 1] + f[k + 1][j]);
                }
            }
        }

        cout << f[1][tot] << endl;
    }

    return 0;
}