[BZOJ 2594] [Wc2006]水管局长数据加强版【LCT】

题目链接：BZOJ - 2594

题目分析

这道题如果没有删边的操作，那么就是 NOIP2013 货车运输，求两点之间的一条路径，使得边权最大的边的边权尽量小。

那么，这条路径就是最小生成树上这两点之间的路径。

然而现在有了删边操作，我们就需要一直维护当前的最小生成树。

删边然后维护 MST 还是不会做的，但是加边维护 MST 就可以用 LCT 来做了。于是，我们将询问和操作都记录下来，离线倒着做，就变成加边了。

加边维护 MST 的做法：

对于新加的一条边 (u, v, w) ，我们先求出现有 MST 中 u 到 v 的路径中，边权最大的边，如果这条边权最大的边的边权大于 w ，我们就将这条边删掉，将新加的边连上，加入 MST 。

否则，我们就忽略新加的这条边。

怎样处理边呢?我们把边看做和两个端点分别相连的一个点，即如果有一条边 (u, v) ，标号为 i ，那么我们就是连边 u -> i -> v ,就可以用 LCT 做了。

技巧：Splay 中一个节点就维护它的子树中边权最大的边的标号就可以了。

写代码时出现的错误：新加入一条边 (u, v, w) 时，发现现有 MST u 到 v 的路径上边权最大的边的边权 > w，需要删掉这条边，然后这条边是 T[t] ，t 是提取出的 u 到 v 的路径的 Splay 的根，

于是我 Cut(u, T[t]); Cut(v, T[t]); 然后就...就 0 分了。因为第一个 Cut 做完之后 T[t] 就改变了啊！！需要先记录下来然后再做两次 Cut ！

代码

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

inline void Read(int &Num)

{

    char c = getchar();

    while (c < '0' || c > '9') c = getchar();

    Num = c - '0'; c = getchar();

    while (c >= '0' && c <= '9')

    {

        Num = Num * 10 + c - '0';

        c = getchar();

    }

}

const int MaxN = 100000 + 5, MaxM = 1000000 + 5, MaxT = 1100000 + 5, MaxQ = 100000 + 5;

int n, m, q, Top, Tot;

int Father[MaxT], Son[MaxT][2], V[MaxT], T[MaxT], f[MaxN], Size[MaxN], Ans[MaxQ];

bool isRoot[MaxT], Rev[MaxT];

struct ES

{

    int u, v, w, Idx;

    bool Del;

} E[MaxM];

struct QR

{

    int f, x, y, Pos;

} Q[MaxQ];

inline bool CmpW(ES e1, ES e2)

{

    return e1.w < e2.w;

}

inline bool CmpIdx(ES e1, ES e2)

{

    return e1.Idx < e2.Idx;

}

inline bool CmpUV(ES e1, ES e2)

{

    return (e1.u < e2.u) || (e1.u == e2.u && e1.v < e2.v);

}

int FindIdx(int x, int y)

{

    if (x > y) swap(x, y);

    int l, r, mid;

    l = 1; r = m;

    while (l <= r)

    {

        mid = (l + r) >> 1;

        if (E[mid].u == x && E[mid].v == y) break;

        if ((E[mid].u < x) || (E[mid].u == x && E[mid].v < y)) l = mid + 1;

        else r = mid - 1;

    }

    return mid;

}

inline int Find(int x)

{

    int i, j, k;

    j = x;

    while (j != f[j]) j = f[j];

    i = x;

    while (i != j)

    {

        k = i;

        i = f[i];

        f[k] = j;

    }

    return j;

}

inline void UN(int x, int y)

{

    if (Size[x] == Size[y]) ++Size[x];

    if (Size[x] > Size[y]) f[y] = x;

    else f[x] = y;

}

/********************* LCT Begin *********************/

inline int gmax(int a, int b) {return V[a] > V[b] ? a : b;}

inline void Update(int x)

{

    T[x] = gmax(x, gmax(T[Son[x][0]], T[Son[x][1]]));

}

inline void Reverse(int x)

{

    Rev[x] = !Rev[x];

    swap(Son[x][0], Son[x][1]);

}

inline void PushDown(int x)

{

    if (!Rev[x]) return;

    Rev[x] = false;

    if (Son[x][0]) Reverse(Son[x][0]);

    if (Son[x][1]) Reverse(Son[x][1]);

}

inline int GetDir(int x)

{

    if (x == Son[Father[x]][0]) return 0;

    else return 1;

}

void Rotate(int x)

{

    int y = Father[x], f;

    PushDown(y); PushDown(x);

    if (x == Son[y][0]) f = 1;

    else f = 0;

    if (isRoot[y])

    {

        isRoot[y] = false;

        isRoot[x] = true;

    }

    else

    {

        if (y == Son[Father[y]][0]) Son[Father[y]][0] = x;

        else Son[Father[y]][1] = x;

    }

    Father[x] = Father[y];

    Son[y][f ^ 1] = Son[x][f];

    if (Son[x][f]) Father[Son[x][f]] = y;

    Son[x][f] = y;

    Father[y] = x;

    Update(y); Update(x);

}

void Splay(int x)

{

    int y;

    while (!isRoot[x])

    {

        y = Father[x];

        if (isRoot[y])

        {

            Rotate(x);

            break;

        }

        if (GetDir(y) == GetDir(x)) Rotate(y);

        else Rotate(x);

        Rotate(x);

    }

}

int Access(int x)

{

    int y = 0;

    while (x != 0)

    {

        Splay(x);

        PushDown(x);

        if (Son[x][1]) isRoot[Son[x][1]] = true;

        Son[x][1] = y;

        if (y) isRoot[y] = false;

        Update(x);

        y = x;

        x = Father[x];

    }

    return y;

}

inline void Make_Root(int x)

{

    int t = Access(x);

    Reverse(t);

}

void Link(int x, int y)

{

    Make_Root(x);

    Splay(x);

    Father[x] = y;

}

void Cut(int x, int y)

{

    Make_Root(x);

    Access(y);

    Splay(y);

    PushDown(y);

    isRoot[Son[y][0]] = true;

    Father[Son[y][0]] = 0;

    Son[y][0] = 0;

    Update(y);

}

/********************* LCT End *********************/

int main()

{

    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= m; ++i)

    {

        Read(E[i].u); Read(E[i].v); Read(E[i].w);

        if (E[i].u > E[i].v) swap(E[i].u, E[i].v);

        E[i].Del = false;

    }

    sort(E + 1, E + m + 1, CmpW); // by ES.w

    for (int i = 1; i <= m; ++i)

    {

        E[i].Idx = i;

        V[n + i] = E[i].w;

    }

    for (int i = 1; i <= n + m; ++i)

    {

        isRoot[i] = true;

        Father[i] = 0;

        T[i] = i;

    }

    sort(E + 1, E + m + 1, CmpUV); // by ES.u && ES.v

    int t;

    for (int i = 1; i <= q; ++i)

    {

        Read(Q[i].f); Read(Q[i].x); Read(Q[i].y);

        if (Q[i].f == 2)

        {

            t = FindIdx(Q[i].x, Q[i].y);

            E[t].Del = true;

            Q[i].Pos = E[t].Idx;

        }

        else ++Top;

    }

    Tot = Top;

    for (int i = 1; i <= n; ++i)

    {

        f[i] = i;

        Size[i] = 1;

    }

    sort(E + 1, E + m + 1, CmpIdx); // by ES.Idx

    int Cnt = 0, fx, fy;

    for (int i = 1; i <= m; ++i)

    {

        if (E[i].Del) continue;

        fx = Find(E[i].u); fy = Find(E[i].v);

        if (fx == fy) continue;

        UN(fx, fy);

        Link(E[i].u, n + i); Link(E[i].v, n + i);

        if (++Cnt == n - 1) break;

    }

    int CutE;

    for (int i = q; i >= 1; --i)

    {

        Make_Root(Q[i].x);

        t = Access(Q[i].y);

        if (Q[i].f == 1) Ans[Top--] = V[T[t]];

        else

        {

            if (E[Q[i].Pos].w >= V[T[t]]) continue;

            CutE = T[t];

            Cut(CutE, E[CutE - n].u); Cut(CutE, E[CutE - n].v);

            Link(Q[i].x, n + Q[i].Pos); Link(Q[i].y, n + Q[i].Pos);

        }

    }

    for (int i = 1; i <= Tot; ++i) printf("%d\n", Ans[i]);

    return 0;

}

巴特西

[BZOJ 2594] [Wc2006]水管局长数据加强版【LCT】

题目分析

代码

最新文章

热门文章

巴特西

[BZOJ 2594] [Wc2006]水管局长数据加强版 【LCT】

题目分析

代码

最新文章

热门文章

[BZOJ 2594] [Wc2006]水管局长数据加强版【LCT】