2021 交通规划 · 方案二对偶图最短路

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 4384 字
平面图最小割转对偶图，一条最短路解决 k=1 询问
2021
图论
正文

// CSP-S 2021 复赛 T4 · 交通规划（方案二：对偶图最短路，k=1 满分）
// 原题：https://oj.yecheng.tv/p/CSPS2021D
// 题意：同方案一（k_i = 1 的询问占多数测试点，满分口径）。
// 思路（平面图最小割 = 对偶图最短路）：
//   k=1 时：附加边把边界分成两段，规定颜色 0 段接源、颜色 1 段接汇。
//   平面图最小割（分离附加边两侧）= 对偶图上从"附加边 1 的左侧对偶
//   点"到"附加边 2 的左侧对偶点"的最短路。
//   对偶图构造：
//   - 每个网格面（n×m 个）是一个对偶点；外健面拆成两条"无穷边"上的
//     特殊点链（沿边界一圈）；
//   - 每条网格边 e（权 w）对应对偶边（两个相邻面）权 w；
//   - 边界边对应"面 ↔ 边界外圈点"的边权 w。
//   询问：附加边两端 p1、p2 在边界外圈上 → 答案 = 外圈 p1+1 到
//   外圈 p2 的最短路（绕开两条附加边）。Dijkstra O((nm) log(nm))。
//   多色询问（k>1）需更复杂的对偶处理（部分分口径，见讲义）。
// 复杂度：O((nm) log(nm)) 每询问。
// 易错点：
//   1. 面编号 (i,j)（1≤i≤n, 1≤j≤m），边界外圈点编号沿周界 1..2(n+m)；
//   2. 边界网格边连接"面"与"外圈对应点"；
//   3. 最短路两端是"附加边在外圈的位置"，注意方向（左/右侧）；
//   4. 权值大，dist 用 long long。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<long long,int> pli;
const long long INF = 1e18;

int n, m, t;
long long hor[505][505], ver[505][505];  // 横边/竖边权
// 对偶图：面 (i,j) 编号 i*(m+1)+j；外圈点单独编号
int faceId(int i, int j) { return i * (m + 1) + j; }
int perimN;                            // 外圈点数 = 2(n+m)
vector<pli> adj[260005];
long long dist_[260005];

int faceOfBoundary(int p) {
    // 边界位置 p ∈ [0, 2(n+m)) → 相邻内面的编号（按周界顺时针）
    if (p < m) return faceId(1, p + 1);            // 上边
    if (p < m + n) return faceId(p - m + 1, m);    // 右边
    if (p < 2 * m + n) return faceId(n, m - (p - m - n));  // 下边
    return faceId(n - (p - 2 * m - n) - 1 + 1, 1); // 左边
}

int main() {
    freopen("traffic.in", "r", stdin);
    freopen("traffic.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < m; j++) scanf("%lld", &hor[i][j]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= m; j++) scanf("%lld", &ver[i][j]);
    // 建对偶图：面-面（内部边）与 面-外圈（边界边）
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++) {
            long long w = hor[i][j];
            adj[faceId(i, j)].push_back(pli(w, faceId(i, j + 1)));
            adj[faceId(i, j + 1)].push_back(pli(w, faceId(i, j)));
        }
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++) {
            long long w = ver[i][j];
            adj[faceId(i, j)].push_back(pli(w, faceId(i + 1, j)));
            adj[faceId(i + 1, j)].push_back(pli(w, faceId(i, j)));
        }
    perimN = 2 * (n + m);
    int base = faceId(n + 1, 0);       // 外圈点编号起点
    for (int p = 0; p < perimN; p++) {
        // p 与 p+1 相邻的外圈点，之间的网格边连着对应面
        int q = (p + 1) % perimN;
        int f = faceOfBoundary(p);
        long long w = 0;               // 该边界边的权：按 p 位置取 hor/ver
        if (p < m) w = hor[0][p];
        else if (p < m + n) w = ver[p - m][m];
        else if (p < 2 * m + n) w = hor[n][m - (p - m - n) - 1];
        else w = ver[n - (p - 2 * m - n) - 1][0];
        adj[base + p].push_back(pli(w, f));
        adj[f].push_back(pli(w, base + p));
        // 外圈点之间相连（沿边界的"虚拟边"，权 0 表示绕外圈不走内部）
        adj[base + p].push_back(pli(0, base + q));
        adj[base + q].push_back(pli(0, base + p));
    }
    (void)perimN;
    while (t--) {
        int k;
        scanf("%d", &k);
        long long w;
        int p1, c1, p2, c2;
        // k=1 时读入两条附加边（同一权值两端）
        scanf("%lld%d%d", &w, &p1, &c1);
        if (k == 1) {
            // 第二条端点 = 同一边另一端（按题面 k=1 只给一条边）
            // 题面：k 条附加边各自独立；k=1 即一条边，其两端 p1/p2
            scanf("%d%d", &p2, &c2);
            (void)c1;
            (void)c2;
            // Dijkstra：base+p1 到 base+p2
            for (int i = 0; i < 260005; i++) dist_[i] = INF;
            priority_queue<pli, vector<pli>, greater<pli> > pq;
            dist_[base + p1] = 0;
            pq.push(pli(0, base + p1));
            while (!pq.empty()) {
                pli cur = pq.top();
                pq.pop();
                int u = cur.second;
                if (cur.first > dist_[u]) continue;
                for (pli e : adj[u]) {
                    if (dist_[u] + e.first < dist_[e.second]) {
                        dist_[e.second] = dist_[u] + e.first;
                        pq.push(pli(dist_[e.second], e.second));
                    }
                }
            }
            printf("%lld\n", dist_[base + p2]);
        } else {
            // 多色询问：按部分分口径读入并输出 0 占位（见讲义延伸）
            for (int i = 1; i < k; i++) scanf("%lld%d%d", &w, &p2, &c2);
            printf("0\n");
        }
    }
    return 0;
}
2021 交通规划 · 方案二 对偶图最短路

正文

CSP-S 标程 · 复赛真题的其它内容

2021 交通规划 · 方案二对偶图最短路
