CSP-S2 2021 T4 交通规划

zimujun · 2021-11-01 16:37:20 · 题解

鸣谢：解题思路来自 ix35。

虽然正解并未涉及网络流算法，但要完成做这道题的转化，甚至是理解题意和解法，需要不少网络流的知识。

发现题意可以转化为：删去每条边都有一个代价，在原图中删去一部分边，使得任意一对白点和黑点不连通。

如果建一个超级源连接所有的白附加点，超级汇连接所有的黑附加点，这样这个转化后的题意就正好符合最小割的定义。可以直接根据最小割最大流定理，在原图上直接跑出最大流求解。

声明：为区分下文中网络流、最短路涉及的不同含义的 s, t，用源、汇代表网络上的两点，起点、终点代表最短路的两点。

大家都做过 bzoj 1001 狼抓兔子吧？

没做也没有关系，这里顺带一提。

这道题的图结构是一个特化的情况，您可以找到一种在平面上重新排布节点位置的方案，使得任意两条边不相交，即图结构是一个平面图。

不妨考虑一下能够作为“割”的一个边集，在这个平面图上会体现出什么样的性质。

可以发现，这个边集内包含的边，至少要覆盖若干个内部的小三角形的两条边，如果用一条曲线连接这些边覆盖过的三角形，则会连出一条从左下直到右上横贯整个图形的线。

图：绿色线代表一个“割”中包含的边，红线代表穿过这些边的线。

因此如果在左下和右上，以源和汇分开的区域放置起点和终点，将内部的每个小三角形视为其它节点，按照原图边权建边，建出对偶图，其起点到终点的最短路就是原图的最小割。

这个做法可以特化本题 k = 2 的部分分上：

（本题平面图结构的对偶图，连接 s, t 和围成的小正方形以及小正方形之间的边是对偶图的边，边权为原图中大致垂直于这条边的连边的代价。）

数据范围加大后，直接网络流的做法复杂度太高，因此只有考虑推广对偶图最短路的做法了。

直接将黑点白点分别连接超级源、超级汇，然后套用 k = 2 的做法是不合适的，因为向超级源汇连去的边可能相交，这时不再容易转化为对偶图最短路。

同样是将最小割转化为最短路，思考一下如果抛开建超级源汇的做法，题目要求您做什么事。

我在上图中构造了一个如果建超级源汇的话会有边相交的情况，即外围出现黑白附加点交替的图结构。这时在外围某块顺逆时针两个方向遇到的第一个附加点颜色不同的连续区间上放置起点和终点，如果逆时针方向上遇到的第一个附加点事白点，就放置一个 s_i，否则放置一个 t_i（当然也可以反过来），其余按照 k = 2 的解法建立对偶图。（上图中红蓝色边块分别代表起点和终点，绿色线代表对偶图的边，橙色粗线代表可能的最短路。）

不难发现，像上图这样，如果每个起点和终点上都至少有一条删除路径与其相连，那么所有的黑点和白点将会被分开。

进一步发现问题的性质：

发现如果某一对起点和终点上连接了超过一条路径（如图中紫色粗线），则多出来的这条路径是赘余的，因为所有的黑白附加点已经被分开了。

因此每个起点只需要找一个唯一的终点贡献它们之间的最短路就够了，换句话说，要实现起点和终点之间代价最小的一一配对，其中匹配的代价为两点之间的最短路。

问题就转化为了：给定一个环，环上点有红蓝两种颜色之分且红蓝点的个数相等，告知红蓝点两两匹配的代价，最小化将红蓝点一一配对的代价之和。

注意到起点和终点的总数只有 \sum k \le 50，因此只需要一个平凡的区间 dp 来求解。

具体的，将环拆成二倍链，设 f(l, r) 表示区间 [l, r] 内所有点已经完成匹配的最小代价和，转移时可以选择直接从 [l + 1, r - 1] 的答案继承过来，也可以枚举中间点拼成这个区间，即：

\displaystyle f(l, r)\leftarrow\min\left\{f(l + 1, r - 1) + dis(node_l, node_r), \min_{l \le mid < r}\{f(l, mid) + f(mid + 1, r)\}\right\}

其中 \leftarrow 表示赋值，node_{pos} 表示映射到状态数组区间上 pos 下标代表的节点，可能为某个起点也可能为某个终点，但 node_l 和 node_r 一定是不同类的点。

此外要注意的一点是，由于只需要求很少点对之间的最短路，因此求解最短路的时候需要跑多次单源最短路而不是一遍全源最短路。

总的复杂度是 O(\sum k_i^3 + nm \log nm\sum k_i) 的。

下面放一下代码吧。其实如果思路清晰了，代码并不难写。

有几个小的细节可以注意一下，可能会让您写代码的时候有更好的体验。

将原图中格子到新图节点编号的映射封装成一个函数；
先加附加点到内部的边，并存图的时候将边的编号初始化 cnt = 1，类似网络流方便取反边。这样每次询问的时候就只需要改一改编号乘 2 和编号乘 2 再加 1 对应边的边权了。
注意数组的含义以确定数组要开多大。否则数组越界访问未知内存的时候可能并不会提示 Runtime Error 而是修改了其他变量的值，这样会给调试增加不少困难，因此要尽量写的时候就多加注意以避免。

下面是删除调试后仍长达 4k 的代码，对应代码块前面写了提示性的注释，应该还有点可读性。

#include <bits/stdc++.h>
#define LL long long

template <typename Temp> inline void read(Temp & rs) {
    Temp fh = 1; rs = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
    for(; isdigit(ch); ch = getchar()) rs = (rs << 3) + (rs << 1) + (ch ^ '0');
    rs = rs * fh; 
}

const int Maxn = 505, N = Maxn * Maxn, M = N * 8;
const LL inf = 1e16;

//EDGE
int ver[M], nxt[M], hd[N], ecnt = 1; LL e[M];
void add(int u, int v, LL w) {
    ecnt++;
    ver[ecnt] = v;
    nxt[ecnt] = hd[u];
    e[ecnt] = w;
    hd[u] = ecnt;
}
void addedge(int u, int v, LL w) {
    add(u, v, w), add(v, u, w);
}

//SSSP
LL dis[N]; std::priority_queue<std::pair<LL, int>> hp; bool vis[N];
void dijkstra(int s) {
    for(int i = 0; i < N; ++i) dis[i] = inf;
    memset(vis, 0, sizeof vis);

    while(!hp.empty()) hp.pop();

    dis[s] = 0, hp.push(std::make_pair(0ll, s));

    while(!hp.empty()) {
        auto p = hp.top(); hp.pop(); int u = p.second; 
        if(vis[u]) continue; vis[u] = 1;

        for(int i = hd[u]; i; i = nxt[i]) {
            int v = ver[i];
            if(dis[u] + e[i] < dis[v] && (!vis[v])) {
                dis[v] = dis[u] + e[i];
                hp.push(std::make_pair(-dis[v], v));
            }
        }
    }
} 

//RANGE DP
const int qMaxk = 105;

LL cost[qMaxk][qMaxk], f[qMaxk][qMaxk];

LL calc(int k) {
    for(int i = 0; i < qMaxk; ++i)
        for(int j = 0; j < qMaxk; ++j)
            f[i][j] = inf;

    int n = k << 1;

    auto g = [k](int x) {
        return (x - 1) % k + 1;
    };

    for(int i = 1; i < n; ++i) f[i][i + 1] = cost[g(i)][g(i + 1)];

    for(int len = 4; len <= k; len += 2) {
        for(int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            f[l][r] = f[l + 1][r - 1] + cost[g(l)][g(r)];
            for(int mid = l + 1; mid < r; mid += 2) {
                f[l][r] = std::min(f[l][r], f[l][mid] + f[mid + 1][r]);
            }
        }
    }

    LL res = 0x7fffffffffffffff;
    for(int i = 1; i <= k; ++i) res = std::min(res, f[i][i + k - 1]);
    return res;
}

//SOLVE
int transid(int x, int y) {
    extern int m; return (x - 1) * m + y;
}

int n, m, q;

struct expt {
    int eid, c; LL len;
} lnk[qMaxk];
int st[qMaxk], ed[qMaxk], cs, ct, lsh[qMaxk], rk[Maxn << 2], cnt;

void query() {
    cs = ct = cnt = 0; for(int i = 1; i <= ((n + m) << 1); ++i) e[i << 1] = e[i << 1 | 1] = 0;

    int k; scanf("%d", &k);
    for(int i = 1; i <= k; ++i) scanf("%lld%d%d", &lnk[i].len, &lnk[i].eid, &lnk[i].c),
    e[lnk[i].eid << 1] = e[lnk[i].eid << 1 | 1] = lnk[i].len;

    std::sort(lnk + 1, lnk + k + 1, [](expt a, expt b) {
        return a.eid < b.eid;
    });


    if(lnk[1].c == 1 && lnk[k].c == 0) st[++cs] = lnk[1].eid, lsh[++cnt] = lnk[1].eid;
    if(lnk[1].c == 0 && lnk[k].c == 1) ed[++ct] = lnk[1].eid, lsh[++cnt] = lnk[1].eid;
    for(int i = 2; i <= k; ++i) {
        if(lnk[i].c == 1 && lnk[i - 1].c == 0) st[++cs] = lnk[i].eid, lsh[++cnt] = lnk[i].eid;
        if(lnk[i].c == 0 && lnk[i - 1].c == 1) ed[++ct] = lnk[i].eid, lsh[++cnt] = lnk[i].eid;// printf("%d ", i);
    }

    std::sort(lsh + 1, lsh + (cs << 1) + 1);
    for(int i = 1; i <= (cs << 1); ++i) rk[lsh[i]] = i;

    if(cs == 0) return printf("0\n"), void();

    for(int i = 0; i < qMaxk; ++i)
        for(int j = 0; j < qMaxk; ++j)
            cost[i][j] = inf;

    for(int i = 1; i <= cs; ++i) {
        dijkstra(st[i]);
        for(int j = 1; j <= ct; ++j) cost[rk[st[i]]][rk[ed[j]]] = cost[rk[ed[j]]][rk[st[i]]] = dis[ed[j]];
    }

    printf("%lld\n", calc(cs << 1));
}

int main() {
    scanf("%d%d%d", &n, &m, &q); LL x;

    for(int i = 1; i < ((n + m) << 1); ++i) addedge(i, i + 1, 0); addedge(2 * (n + m), 1, 0);
    int delta = (n + m) << 1;

    for(int i = 1; i < n; ++i)
        for(int j = 1; j <= m; ++j) {
            scanf("%lld", &x);
            if(j == 1) addedge(2 * (m + n) + 1 - i, delta + transid(i, j), x);
            else if(j == m) addedge(m + 1 + i, delta + transid(i, j - 1), x);
            else addedge(delta + transid(i, j - 1), delta + transid(i, j), x);
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < m; ++j) {
            scanf("%lld", &x);
            if(i == 1) addedge(1 + j, delta + transid(i, j), x);
            else if(i == n) addedge(2 * m + n + 1 - j, delta + transid(i - 1, j), x);
            else addedge(delta + transid(i - 1, j), delta + transid(i, j), x);
        }
    while(q--) query();
    return 0;
}