[CSP-S 2021] 交通规划题解

· · 题解

仔细读了十遍题面，硬是一个字都没和交通规划扯上关系，很有可能是出题人编了一个故事，发现编不下去了。

首先这是一个最小割的问题，需要学习超纲算法来骗分，建图后用dinic算法求最大流实测可以得到 60 分。

正解需要把平面图最小割转换成对偶图最短路问题。这 n+m 条直线可以把平面划分成 (n+1)\times(m+1) 个区域，我们把这每个区域看成一个结点来建一张新图，相邻两个区域之间的边权即为新图中两个结点之间的边权。

注意外面这一圈有 2m+2n 个无穷大区域比较特殊，我们需要对他们分类及编号，然后求最短路。

当所有附加点颜色相同时，答案为 0，这种情况后面就不讨论了。

当 k=2 时，外面这一圈区域被划分成两个部分，附加点的颜色顺时针从 0 到 1 为第一个部分，从 1 到 0 是第二个部分，此时只需求这两个部分的最短路即可。

当 k>2 时，找到某一个顺时针 0 到 1 的部分把这些结点编为 1 号块 ，然后继续按顺时针找到 1 到 0 的部分编号为 2 号块，接着继续按顺时针找到 0 到 1 的部分把这些结点编号为 3 号块……

注意 0 到 0 以及 1 到 1 的部分不需要编成块，因为不会在这里面割。这样，外面一圈区域最终会划分成偶数个块，割只会产生在两个奇偶性不同的块之间，而且不会有交叉。（以上结论的具体证明略，可以画图尝试一下）

这样，只需跑最多 25 次 Dijkstra 算法，处理出g[i][j]表示第 i 个块到第 j 个块的最短路。但具体是哪两个块配对还未知，由于不会有交叉，可以用类似三角剖分的区间 DP 求出总共的最小值。

定义f[i][j]表示 [i,j] 这段区间内的块都配队完的最短路最小和值，转移即为 f_{i,j}=\min\{g_{i,k} + f_{i+1,k-1} + f_{k+1,j}\}，含义就是第 i 块和第 k 块配对，然后分成两部分。

说了那么多，有不理解的地方建议参考下面的代码，最复杂的部分应该是结点的编码部分，以及顺时针把外圈分成块的部分，有很多细节要考虑清楚。这题我也写的很久，大概有 180 行。

总时间复杂度 O(k^3+knm\log(nm))，代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 260000;

struct Edge {
    int v, w, next;
} e[N * 10];
int h[N], _h[N], eid;
void addEdge(int u, int v, int w) {
    e[eid] = {v, w, h[u]};
    h[u] = eid++;
}

int n, m, _;
int a[2005], c[2005];
vector<int> zoo;       //外面一圈的编号
int b[N], tot;         //tot表示块号 b表示外面一圈点属于的块号
vector<int> pig[100];  //每块的结点编号
int d[N], vis[N];
struct Node {
    int u, d;
    bool operator<(const Node &rhs) const {
        return d > rhs.d;
    }
};
int g[100][100], f[100][100];
void dijk(int s) {
    memset(d, 0x3f, sizeof d);
    memset(vis, 0, sizeof vis);
    priority_queue<Node> q;
    for (auto x : pig[s]) {
        d[x] = 0;
        q.push({x, 0});
    }
    int cnt = 0; // 无聊加了一个优化，不是很有必要，但是效果明显
    while (q.size() && 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]] = d[u], cnt++; 
        for (int i = h[u]; ~i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({v, d[v]});
            }
        }
    }
}
int id(int x, int y) {
    return x * (m + 1) + y;
}
// 通过射线编号找顺时针下一个结点编号
int id2(int x) {
    if (x <= m) {
        return id(0, x);
    } else if (x <= m + n) {
        x -= m;
        return id(x, m);
    } else if (x <= m + n + m) {
        x -= m + n;
        x = m - x + 1;
        return id(n, x - 1);
    } else {
        x -= m + n + m;
        x = n - x + 1;
        return id(x - 1, 0);
    }
}
int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &_);
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            int u = id(i, j - 1), v = id(i, j), w;
            scanf("%d", &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            int u = id(i - 1, j), v = id(i, j), w;
            scanf("%d", &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
    }

    for (int u = 0; u < 2; u++) {
        for (int i = 0; i <= m; i++) zoo.push_back(id(0, i));
        for (int i = 1; i <= n - 1; i++) zoo.push_back(id(i, m));
        for (int i = m; i >= 0; i--) zoo.push_back(id(n, i));
        for (int i = n - 1; i >= 1; i--) zoo.push_back(id(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++) pig[i].clear();
        tot = 0;
        int TT;
        scanf("%d", &TT);
        int flag = 0;
        for (int i = 0; i < TT; i++) {
            int x, p, t;
            scanf("%d%d%d", &x, &p, &t);
            a[p] = x, c[p] = t;
            flag |= 1 << t;
        }
        if (flag != 3) {
            puts("0");
            continue;
        }
        for (int i = 1; i <= m; i++) {
            int u = id(0, i - 1), v = id(0, i);
            addEdge(u, v, a[i]);
            addEdge(v, u, a[i]);
        }
        for (int i = 1; i <= n; i++) {
            int u = id(i - 1, m), v = id(i, m);
            addEdge(u, v, a[i + m]);
            addEdge(v, u, a[i + m]);
        }
        for (int i = 1; i <= m; i++) {
            int u = id(n, m - i + 1), v = id(n, m - i);
            addEdge(u, v, a[i + m + n]);
            addEdge(v, u, a[i + m + n]);
        }
        for (int i = 1; i <= n; i++) {
            int u = id(n - i + 1, 0), v = id(n - i, 0);
            addEdge(u, v, a[i + m + n + m]);
            addEdge(v, u, a[i + m + n + m]);
        }
        for (int i = 1; i <= 2 * n + 2 * m; i++) {
            if (c[i] == -1) continue;
            for (int j = i + 1;; j++) {
                if (j > 2 * n + 2 * m) j = 1;
                if (c[j] == -1) continue;
                if (c[j] != c[i]) {
                    tot++;
                    int x = id2(i), y = id2(j);
                    int flag = 0;
                    for (auto u : zoo) {
                        if (u == x) flag = 1;
                        if (flag) {
                            if (u == y) break;
                            b[u] = tot;
                            pig[tot].push_back(u);
                        }
                    }
                }
                break;
            }
        }

        for (int i = 1; i <= tot; i++) {
            dijk(i);
        }
        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] + f[i + 1][k - 1] + f[k + 1][j]);
                }
            }
        }
        printf("%d\n", f[1][tot]);
    }
    return 0;
}