并查集不用多说了,就是合并两个子集+路径压缩,在并查集上加上可持久化的话,就是说要有历史版本的存在,每更改一次集合,就要新建一个并查集。不可能把每一个点都复制一遍来新建一个集合,因为每次更改只会修改一个点的父亲是谁,所以只需修改这个点就行了,这也是可持久化的基本思想。因此,可持久化并查集无法在使用路径压缩,因为路径压缩会修改不止一个点,还会修改路径上的所有点,这样的话在可持久化数据结构中,修改的数据可能是被多个版本的并查集共同拥有的,修改会引发更多的麻烦。

不同于原来的并查集,可持久化需要借助线段树这个数据结构,在0号版本的并查集构成的线段树中,只有叶子结点有权值,其余结点都只保存左右孩子结点信息。每个叶子结点的权值就是这个结点在并查集意义上的父亲,不是线段树上的。也就是说所有叶子节点和其权值可以构成一个森林,这个森林就是当前版本的并查集。

那么每一次修改就是合并两个集合,也就是在旧版本的线段树中修改一个叶子结点的权值,而且修改的那个叶子结点的权值在数值上一定是它本身。至于修改两个集合中哪一个的根结点是可持久化并查集的核心。。我们知道一个并查集包含一些集合,每个集合可以表示成一棵树,并且有一个代表这个集合的根结点,而每棵树都会有一个深度,当我们不采用路径压缩时,这个深度就决定了每次查询的时间复杂度,当然是最大深度越小越好。

根据以上分析,我们给每个叶子结点安排一个深度权值,这个权值表示这个结点在并查集意义下,其所在集合所构成的树中,该结点到它所有的孩子结点中最远的那一个的距离,当然这个最远的那一个肯定是叶子结点。因为我们说过可持久化并查集是很难去路径压缩的,所以在每次合并两个集合的时候就应该尽可能是所有结点的最大深度权值尽可能地小。那么对于要合并的两个集合,把根结点深度小的那个集合并到深度大的上面就行了,这样深度大的结点深度不用改变,只有在这个根结点的深度一样的情况下,才会有深度+1的操作。

可持久化并查集的时间复杂度为O(n(logn)^2),空间复杂度O(nlogn)

题目
P3402 可持久化并查集
先输入n和m,表示初始集合个数和操作数。
三种操作:
1 a b:合并ab所在集合
2 k:回到第k次操作后
3 a b:询问ab是否在一个集合内
做这题的时候,由于当ab在一个集合内时,就不用合并,忘了给root[i]赋值,导致卡了很久。。。我调代码的能力真的是越来越废了...

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5+5;
int n, m;

struct zyh {
    int l, r;
    int fa, deep;
}tree[maxn*30];

int root[maxn*2], top;       // root[i]表示第i个版本的树根位置,top表示数据池使用情况

int build(int l, int r) {
    int tmp = ++top;
    if (l==r) {
        tree[tmp].fa = l;
        tree[tmp].deep = 0;
        return tmp;
    }
    int mid = (l+r) >> 1;
    tree[tmp].l = build(l, mid);
    tree[tmp].r = build(mid+1, r);
    return tmp;
}

int find(int x, int edt) {       // 寻找edt版本下x的根结点
    int l=1, r=n, mid, now = root[edt];
    while (l<r) {
        mid = (l+r) >> 1;
        if (x<=mid) {
            r=mid;
            now = tree[now].l;
        }else {
            l=mid+1;
            now = tree[now].r;
        }
    }
    if (tree[now].fa != l)  return find(tree[now].fa, edt);
    return now;
}
// x表示源结点, lr为区间信息,k为要修改的结点,w为修改的值,然后返回在x版本上修改后得到的新结点
// flag 表示修改的数据类型,flag=1表示只改fa,flag=2表示只改deep,改为deep+1
int add(int x, int l, int r, int k, int w, int flag) {
    int tmp = ++top;
    if (l==r) {
        if (1==flag) {
            tree[tmp].fa = w;
            tree[tmp].deep = tree[x].deep;
        }else {
            tree[tmp].fa = tree[x].fa;
            tree[tmp].deep = tree[x].deep + 1;
        }
        return tmp;
    }
    int mid = (l+r) >> 1;
    if (k<=mid) {
        tree[tmp].r = tree[x].r;
        tree[tmp].l = add(tree[x].l, l, mid, k, w, flag);
    }else {
        tree[tmp].l = tree[x].l;
        tree[tmp].r = add(tree[x].r, mid+1, r, k, w, flag);
    }
    return tmp;
}

int main() {
    //freopen("in.txt", "r", stdin);
    int a, b, opt, k;
    scanf ("%d %d", &n, &m);
    //top = 5;
    root[0] = build(1, n);
    for (int i=1; i<=m; i++) {
        scanf ("%d", &opt);
        if (1==opt) {
            scanf ("%d %d", &a, &b);
            int f1 = find(a, i-1), f2 = find(b, i-1);
            root[i] = root[i-1];
            if (tree[f1].fa == tree[f2].fa) 
                continue;

            if (tree[f1].deep > tree[f2].deep) {
                root[i] = add(root[i], 1, n, tree[f2].fa, tree[f1].fa, 1);
            } else if (tree[f1].deep < tree[f2].deep) {
                root[i] = add(root[i], 1, n, tree[f1].fa, tree[f2].fa, 1);
            } else {
                root[i] = add(root[i], 1, n, tree[f2].fa, tree[f1].fa, 1);
                root[i] = add(root[i], 1, n, tree[f1].fa, tree[f1].fa, 2);
            }
        }else if (2==opt) {
            scanf ("%d", &k);
            root[i] = root[k];
        }else {
            root[i] = root[i-1];
            scanf ("%d %d", &a, &b);
            if (tree[find(a, i)].fa == tree[find(b, i)].fa)   puts ("1");
            else    puts("0");
        }
    }
    return 0;
}
P4768 [NOI2018] 归程

T组数据,每组数据给定一个无向图,n个点,m条边,每条边有两个属性:长度l和海拔a。Q次询问,每次询问给一个起始点v和海拔限制p,只有那些海拔大于p的边才可以开车走,所有的边都可以步行经过,对于每次询问,输出从结点v到结点1需要步行的最短距离。车不能走海拔小于等于p的边,但是可以步行,而且当下车开始步行后就再也不能开车了。询问之间相互独立。

根据题意,每一次询问都相当于把海拔大于p的边加入图中,若加入后v和1在同一个连通块内,那么答案就是0,否则答案等于该结点所在连通块内所有结点步行到1号结点的最短距离。

这个思路是正确的,那么实现代码的话,就先把图输入,然后求一个最短路(Dijkstra),把每个点步行到1号结点的最短距离保存,做为一个权值。然后建立可持久化并查集,把图的所有边按海拔从大到小排序,然后依次加入到图中,相当于是合并两个集合,每加入一条边就新建一个版本的并查集。而且并查集中每个集合都要维护最短路信息(就是这个集合中的点步行到1号结点的最短路程)。全部处理完成之后,对于每次询问,先二分查找哪些边是大于p的,我们需要访问哪个版本的并查集,然后直接输出v所在集合的最短路程这个权值就行了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+5, maxm = 4e5+5, inf = 2147483647;

// 建图所用数据,以及最短路
int n, m;
vector<int> G[maxn], w[maxn];
int dist[maxn];
bool vis[maxn];
typedef struct zyh1{
    int pos;
    int dist;
    friend bool operator < (const struct zyh1 &a, const struct zyh1 &b) {
        return a.dist > b.dist;
    }
}node;
priority_queue<node> q;

// 可持久化并查集部分..
// 把图中边的海拔从大到小排序后,每次加入一条边到图中,并对并查集进行操作。
// 并查集要维护的是 某个子集合中所有点到1号结点的最短dist
struct zyh2 {
    int l, r;
    int fa, deep;
    int dist;
}tree[maxn*50];
int top, root[maxm];
struct zyh3 {
    int u, v, l, a;
    zyh3(int u, int v, int l, int a) {
        this->u = u, this->v = v;
        this->l = l, this->a = a;
    }
    zyh3(){}
}edges[maxm];
bool cmp(const struct zyh3 &a, const struct zyh3 &b) {
    return a.a > b.a;
}

inline int read() {
    int x=0, f=1;
    char ch=getchar();
    while (ch>'9' || ch<'0') {
        if (ch=='-')    f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9') {
        x = x*10 + ch-'0';
        ch=getchar();
    }
    return x*f;
}

void Dijkstra(int s, int dist[], vector<int> G[], vector<int> w[]) {
    for (int i=1; i<=n; i++)    dist[i] = inf, vis[i] = 0;
    dist[s] = 0;
    q.push(node{s, 0});
    node tmp;
    while (!q.empty()) {
        tmp = q.top();    q.pop();
        if (vis[tmp.pos])   continue;
        vis[tmp.pos] = 1;
        for (int i=0; i<G[tmp.pos].size(); i++) {
            if (dist[G[tmp.pos][i]] > tmp.dist + w[tmp.pos][i]) {
                dist[G[tmp.pos][i]] = tmp.dist + w[tmp.pos][i];
                q.push(node{G[tmp.pos][i], dist[G[tmp.pos][i]]});
            }
        }
    }
    return;
}

int build(int l, int r) {
    int tmp = ++top;
    if (l==r) {
        tree[tmp].fa = l;
        tree[tmp].deep = 0;
        tree[tmp].dist = dist[l];
        return tmp;
    }
    int mid = (l+r) >> 1;
    tree[tmp].l = build(l, mid);
    tree[tmp].r = build(mid+1, r);
    return tmp;
}

int find (int x, int edt) {
    int l=1, r=n, mid, now = root[edt];
    while (l<r) {
        mid = (l+r) >> 1;
        if (x<=mid) {
            r = mid;
            now = tree[now].l;
        }else {
            l = mid+1;
            now = tree[now].r;
        }
    }
    if (tree[now].fa != l)  return find(tree[now].fa, edt);
    return now;
}

// 3种操作,修改某个点的父亲,修改某个点的dist,修改某个点的deep和dist。
int add(int x, int l, int r, int k, int w, int flag) {
    int tmp = ++top;
    if (l==r) {
        tree[tmp].fa = tree[x].fa;
        tree[tmp].deep = tree[x].deep;
        tree[tmp].dist = tree[x].dist;
        if (1==flag) {
            tree[tmp].fa = w;
        }else if (2==flag){
            tree[tmp].dist = w;
        }else {
            tree[tmp].dist = w;
            tree[tmp].deep += 1;
        }
        return tmp;
    }
    int mid = (l+r) >> 1;
    if (k<=mid) {
        tree[tmp].l = add(tree[x].l, l, mid, k, w, flag);
        tree[tmp].r = tree[x].r;
    }else {
        tree[tmp].l = tree[x].l;
        tree[tmp].r = add(tree[x].r, mid+1, r, k, w, flag);
    }
    return tmp;
}

int src(int x) {
    if (edges[1].a <= x) return 0;
    int l=1, r=m, mid;
    while (l<r) {
        mid = ((l+r) >> 1) + ((l+r)&1);
        if (edges[mid].a>x)    l=mid;
        else    r = mid-1;
    }
    return l;
}

int main() {
    int t, u, v, l, a;
    int Q, K, S;
    t = read();
    while (t--) {
        top = 0;
        n = read(), m = read();
        for (int i=1; i<=n; i++) {
            G[i].clear();
            w[i].clear();
        }
        for (int i=1; i<=m; i++) {
            u = read(), v = read();
            l = read(), a = read();
            G[u].push_back(v);
            w[u].push_back(l);
            G[v].push_back(u);
            w[v].push_back(l);
            edges[i] = *(new zyh3(u, v, l, a));
        }
        Dijkstra(1, dist, G, w);

        sort (edges+1, edges+m+1, cmp);
        root[0] = build(1, n);
        for (int i=1; i<=m; i++) {
            int f1 = find(edges[i].u, i-1), f2 = find(edges[i].v, i-1);
            root[i] = root[i-1];
            if (tree[f1].fa == tree[f2].fa)  continue;
            int tmp = min(tree[f1].dist, tree[f2].dist);
            if (tree[f1].deep > tree[f2].deep) {
                root[i] = add(root[i-1], 1, n, tree[f2].fa, tree[f1].fa, 1);
                root[i] = add(root[i], 1, n, tree[f1].fa, tmp, 2);
            }else if (tree[f1].deep < tree[f2].deep){
                root[i] = add(root[i-1], 1, n, tree[f1].fa, tree[f2].fa, 1);
                root[i] = add(root[i], 1, n, tree[f2].fa, tmp, 2);
            }else {
                root[i] = add(root[i-1], 1, n, tree[f2].fa, tree[f1].fa, 1);
                root[i] = add(root[i], 1, n, tree[f1].fa, tmp, 3);
            }
        }
        Q = read(), K = read(), S = read();
        int lastans = 0, v, p;
        for (int i=1; i<=Q; i++) {
            v = (read() + K*lastans-1)%n+1;
            p = (read() + K*lastans)%(S+1);
            int edt = src(p);
            int f = find(v, edt);
            lastans = tree[f].dist;
            printf ("%d\n", lastans);
        }
    }
    return 0;
}

0 条评论

发表评论

邮箱地址不会被公开。