首页 > 其他 > 详细

【SDOI2019】世界地图 - 题解

时间:2019-05-23 14:17:54      阅读:191      评论:0      收藏:0      [点我收藏+]

题目链接

【SDOI2019】世界地图

做法

因为 $ n $ 很小,所以问题可以从 $ n $ 入手。
发现询问不会删除第一列和最后一列,那么最后的结果为合并地图 $ [1, l_i - 1] $ 和 $ [r_i + 1, m] $ 的 $ MST $ 得到的 $ MST $ 大小。所以预处理只要求地图前缀/后缀 $ MST $ 即可。
考虑如何合并两个相邻的 $ MST $ 。发现合并这两个 $ MST $ 只有最前和最后两列的点会产生连接的关系,所以每个 $ MST $ 只要记录两端的点构成的虚树(虚树边权为两点之间路径的最大值),然后再用 $ Kruskal $ 建最小生成树即可。
时间复杂度 $ O(n(m + q) \log n) $ 。

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 20010, M = 510;
int n, m, lim, q;
unsigned int SA, SB, SC;
int rht[N][M], dwn[N][M];

struct Edge {
    int x, y, w;
    Edge(int X, int Y, int W) : x(X), y(Y), w(W) {}
    inline bool operator<(const Edge &yy)const { return w < yy.w; }
};

int tot, fa[N], flag[N]; vector<Edge> e; ll ad;
int cnt = 0, hed[N], to[N], nxt[N], val[N];

struct MST {
    int tot; ll sum; vector<Edge> e; MST() {}
    MST(int *ar) {
        tot = n, sum = 0;
        for(int i = 1; i < n; i++) e.pb(Edge(i, i + 1, ar[i]));
    }
    ll qry() { ll ss = sum; for(auto v : e) ss += v.w; return ss; }
}; MST pre[N], suf[N];

inline int Max(const int &x, const int &y) { return x > y ? x : y; }
int gi() {
    SA ^= SA << 16, SA ^= SA >> 5, SA ^= SA << 1; unsigned int t = SA;
    SA = SB, SB = SC, SC ^= t ^ SA; return SC % lim + 1;
}
void gen() {
    scanf("%d%d%u%u%u%d", &n, &m, &SA, &SB, &SC, &lim);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) rht[j][i] = gi();
    for(int i = 1; i < n; i++) for(int j = 1; j <= m; j++) dwn[j][i] = gi();
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void lnk(const Edge &x) {
    to[++cnt] = x.y, val[cnt] = x.w, nxt[cnt] = hed[x.x], hed[x.x] = cnt;
    to[++cnt] = x.x, val[cnt] = x.w, nxt[cnt] = hed[x.y], hed[x.y] = cnt;
    ad += x.w, fa[find(x.x)] = find(x.y);
}
int dfs1(int u, int ff) {
    int ss = 0;
    for(int i = hed[u]; i; i = nxt[i]) if(to[i] != ff) ss += dfs1(to[i], u);
    if(ss >= 2) flag[u] = 1; ss += flag[u]; return ss > 0;
}
void dfs2(int u, int ff, int lst, int ww) {
    if(flag[u]) {
        if(lst) e.pb(Edge(flag[u], lst, ww));
        lst = flag[u], ad -= ww, ww = 0;
    }
    for(int i = hed[u]; i; i = nxt[i])
        if(to[i] != ff) dfs2(to[i], u, lst, Max(ww, val[i]));
}
MST merge(const MST &x, const MST &y, int *ar) {
    tot = x.tot + y.tot, e.clear();
    for(auto v : x.e) e.pb(v);
    for(auto v : y.e) e.pb(Edge(v.x + x.tot, v.y + x.tot, v.w));
    for(int i = 1; i <= n; i++)
        e.pb(Edge(x.tot - n + i, x.tot + i, ar[i]));
    sort(e.begin(), e.end()), cnt = 0, ad = 0;
    for(int i = 1; i <= tot; i++)
        fa[i] = i, flag[i] = (i <= n || i > tot - n), hed[i] = 0;
    for(auto v : e) if(find(v.x) != find(v.y)) lnk(v);
    dfs1(1, 0), cnt = 0;
    for(int i = 1; i <= tot; i++) if(flag[i]) flag[i] = ++cnt;
    e.clear(), dfs2(1, 0, 0, 0);
    MST res; res.tot = cnt, res.e = e, res.sum = x.sum + y.sum + ad;
    return res;
}
int main() {
    gen();
    pre[1] = MST(dwn[1]);
    for(int i = 2; i < m; i++)
        pre[i] = merge(pre[i - 1], MST(dwn[i]), rht[i - 1]);
    suf[m] = MST(dwn[m]);
    for(int i = m - 1; i > 1; i--)
        suf[i] = merge(MST(dwn[i]), suf[i + 1], rht[i]);
    scanf("%d", &q);
    for(int l, r; q; --q) {
        scanf("%d%d", &l, &r);
        printf("%lld\n", merge(suf[r + 1], pre[l - 1], rht[m]).qry());
    }
    return 0;
}

【SDOI2019】世界地图 - 题解

原文:https://www.cnblogs.com/daniel14311531/p/10911377.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!