T3-19 Not Splitting

思路解析

问题本质

在 k×k 网格中，沿网格线切割将其分成两个连通且全等的部分。给定 n 个相邻格子对，求最多能选多少对使它们都在同一部分内。

关键观察

观察 1：有效切割一定是 180° 中心对称的。

k 为偶数，网格中心恰好是格线交点 (k/2, k/2)。要使两部分全等，切割路径必须关于中心 180° 对称。因此切割路径从边界经过中心到对面边界。

观察 2：转化为最短路。

一个相邻格子对"不被满足"当且仅当两格之间的格线段在切割路径上。我们希望最小化被切割的对数，答案就是 n 减去这个最小值。

观察 3：利用对称性减半。

由于路径 180° 对称，只需确定从中心到边界的半条路径，另一半由对称决定。对于半路径上的每条格线段 e，它和它的 180° 对称边 mirror(e) 同时出现在完整路径上，代价为 count(e) + count(mirror(e))。

算法

1. 统计每条格线段被多少个输入对跨越
2. 构建格线交点图，每条边权 = 自身计数 + 对称边计数
3. 从中心 (k/2, k/2) 跑 Dijkstra 到任意边界点
4. 答案 = n − 最短路距离

---

坐标映射详解

格线交点用 (i, j) 表示，$0 \le i, j \le k$。

输入对 → 格线段：

• 水平相邻对 (r, c₁)-(r, c₂)（c₂=c₁+1）→ 竖直格线段 down_edge(r−1, c₁)
• 竖直相邻对 (r₁, c)-(r₂, c)（r₂=r₁+1）→ 水平格线段 right_edge(r₁, c−1)

180° 对称映射：

• right_edge(i, j) 的对称边 = right_edge(k−i, k−j−1)
• down_edge(i, j) 的对称边 = down_edge(k−i−1, k−j)

---

逐行注释代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);

        // cr[i][j]: 跨越 right_edge(i,j) 的输入对数量（水平格线段）
        // cd[i][j]: 跨越 down_edge(i,j) 的输入对数量（竖直格线段）
        vector<vector<int>> cr(k + 1, vector<int>(k, 0));
        vector<vector<int>> cd(k, vector<int>(k + 1, 0));

        for (int p = 0; p < n; p++) {
            int r1, c1, r2, c2;
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);

            if (r1 == r2) {                        // 水平相邻
                int cm = min(c1, c2);              // 列号较小的
                cd[r1 - 1][cm]++;                  // 对应竖直格线段
            } else {                               // 竖直相邻
                int rm = min(r1, r2);              // 行号较小的
                cr[rm][c1 - 1]++;                  // 对应水平格线段
            }
        }

        // ========== Dijkstra：从中心到边界 ==========
        int cx = k / 2, cy = k / 2;               // 中心格线交点
        int total = (k + 1) * (k + 1);            // 格线交点总数
        auto id = [&](int i, int j) {             // 二维坐标 → 一维编号
            return i * (k + 1) + j;
        };

        vector<int> dist(total, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

        dist[id(cx, cy)] = 0;                     // 中心距离为 0
        pq.push({0, id(cx, cy)});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;             // 过时状态跳过

            int i = u / (k + 1), j = u % (k + 1); // 还原二维坐标

            // 向右走：使用 right_edge(i, j)
            // 权重 = 自身计数 + 180°对称边 right_edge(k-i, k-j-1) 的计数
            if (j < k) {
                int w = cr[i][j] + cr[k - i][k - j - 1];
                int v = id(i, j + 1);
                if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
            }

            // 向左走：使用 right_edge(i, j-1)
            // 对称边为 right_edge(k-i, k-j)
            if (j > 0) {
                int w = cr[i][j - 1] + cr[k - i][k - j];
                int v = id(i, j - 1);
                if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
            }

            // 向下走：使用 down_edge(i, j)
            // 对称边为 down_edge(k-i-1, k-j)
            if (i < k) {
                int w = cd[i][j] + cd[k - i - 1][k - j];
                int v = id(i + 1, j);
                if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
            }

            // 向上走：使用 down_edge(i-1, j)
            // 对称边为 down_edge(k-i, k-j)
            if (i > 0) {
                int w = cd[i - 1][j] + cd[k - i][k - j];
                int v = id(i - 1, j);
                if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
            }
        }

        // ========== 找边界点的最短距离 ==========
        int min_cut = INT_MAX;
        for (int i = 0; i <= k; i++) {
            min_cut = min(min_cut, dist[id(0, i)]);   // 上边界
            min_cut = min(min_cut, dist[id(k, i)]);   // 下边界
            min_cut = min(min_cut, dist[id(i, 0)]);   // 左边界
            min_cut = min(min_cut, dist[id(i, k)]);   // 右边界
        }

        // 答案 = 总对数 - 被切割的最少对数
        printf("%d\n", n - min_cut);
    }
    return 0;
}