题解 P4172 【[WC2006]水管局长】

cirnovsky · 2020-01-28 21:21:02 · 题解

SC 省 MY 市有着庞大的地下水管网络，嘟嘟是 MY 市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从 x 处送往 y 处，嘟嘟需要为供水公司找到一条从 A 至 B 的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。

在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于 MY 市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。

不妨将 MY 市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。

这道题只有删边操作，我们可以把这个过程看做是加边操作，这样好处理一点。

题目保证了图无论怎么删边都保证联通，所以我们可以先把图删完。删完后我们呢求出图的MST, 那么任意两点在这颗MST上走都是最优的别问我怎么证贪心是用来证的吗。我们可以用LCT来维护这颗MST，Splay维护区间最大值(也就是链上的最大值)

考虑加边操作。上面我提到了一个贪心：任意两点在这颗MST上走都是最优的。如果此时我们在MST上任意加一条边都会形成一个环。我们可以从任意一点入环，任意一点出环，方向随意。可以发现我们的最优解始终能避开最长的一条边！

考察这个环，用lct的split操作提出链的信息，查出最大的权值。发现我们可以通过删除权值最大的边来保证环上的最优。

怎么求出这条边呢？显然我们可以二分来找

再来考虑一个问题：如何维护边呢？

考虑用一个点来表示一条边。

最后逆序加边，把答案逆序输出即可

(良心题解)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#define mid ((l + r) >> 1)
#define mp make_pair
#define fir first
#define sec second
#define pub push_back
#define pob pop_back

using namespace std;
typedef long long LL;

#define io_e '\0'
#define io_s ' '
#define io_l '\n'
 #define _DEBUG_ 1 // debug toggle
namespace Fast_IO {
#ifndef _DEBUG_
    #define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#else
    #define gc() getchar()
#endif
    const int SIZ = 1 << 21 | 1;
    char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110], c;
    int fr;
    inline void ioout() {
        fwrite(obuff, 1, oS - obuff, stdout);
        oS = obuff;
    }
    template <class Type>
    inline void read(Type& x) {
        x = 0;
        Type y = 1;
        for (c = gc(); (c > '9' || c < '0') && c ^ '-'; c = gc())
            ;
        c == '-' ? y = -1 : x = (c & 15);
        for (c = gc(); c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c & 15);
        x *= y;
    }
    inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
    inline void read(char* s) {
        register char ch = gc();
        for (; blank(ch); ch = gc())
            ;
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }
    inline void read(char& c) {
        for (c = gc(); blank(c); c = gc())
            ;
    }
    template <typename Type, typename... Args>
    inline void read(Type& t, Args&... args) {
        read(t), read(args...);
    }
    template <typename... Args>
    inline void read(char* t, Args&... args) {
        read(t), read(args...);
    }
    template <typename... Args>
    inline void read(char& t, Args&... args) {
        read(t), read(args...);
    }
    template <class Type>
    inline void write(char lastChar, Type x) {
        if (x < 0)
            *oS++ = '-', x = -x;
        if (x == 0)
            *oS++ = '0';
        while (x) fu[++fr] = x % 10 + '0', x /= 10;
        while (fr) *oS++ = fu[fr--];
        *oS++ = lastChar;
        ioout();
    }
    inline void write(char lastChar, char x[]) {
        for (register int i = 0; x[i]; ++i) *oS++ = x[i];
        *oS++ = lastChar;
        ioout();
    }
    inline void write(char lastChar, char x) {
        *oS++ = x;
        *oS++ = lastChar;
        ioout();
    }
    template <typename Type, typename... Args>
    inline void write(char midChar, Type t, Args... args) {
        write(midChar, t), write(midChar, args...);
    }
}  // namespace Fast_IO

using Fast_IO::read;
using Fast_IO::write;

namespace LinkCutTree {
    const int SIZE = 12e4 + 5;
    struct SPLAY {
        int ch[2];
        int fa;
        int key;
        int maxValue;
        int lazyTag;
    } T[SIZE];
    stack < int > MemoryWaste; 
    #define ls T[x].ch[0]
    #define rs T[x].ch[1]
    #define WhichSon(x) (T[T[x].fa].ch[1] == x)
    #define IsRoot(x) (T[T[x].fa].ch[0] ^ x && T[T[x].fa].ch[1] ^ x)

    void UpdateMessage(int x) {
        T[x].maxValue = max(max(T[ls].maxValue, T[x].key), T[rs].maxValue);
    }

    void UpdateSons(int x) {
        if (T[x].lazyTag) {
            ls ^= rs ^= ls ^= rs;
            T[x].lazyTag = 0;
            T[ls].lazyTag ^= 1;
            T[rs].lazyTag ^= 1;
        }
    }

    void RotateNode(int x) {
        int y = T[x].fa;
        if (!IsRoot(y)) T[T[y].fa].ch[WhichSon(y)] = x;
        bool k = WhichSon(x);
        T[x].fa = T[y].fa;
        T[y].fa = x;
        T[y].ch[k] = T[x].ch[k ^ 1];
        T[T[y].ch[k]].fa = y;
        T[x].ch[k ^ 1] = y;
        UpdateMessage(y);
        UpdateMessage(x);
    }

    void LinkSplay(int x) {
        int u = x;
        while (!IsRoot(u)) MemoryWaste.push(u), u = T[u].fa;
        MemoryWaste.push(u);
        while (MemoryWaste.size()) UpdateSons(MemoryWaste.top()), MemoryWaste.pop();
        for (; !IsRoot(x); RotateNode(x)) {
            int y = T[x].fa;
            if (!IsRoot(y))
                RotateNode(WhichSon(x) ^ WhichSon(y) ? x : y);
        }
    }
    void AccessEdge(int x) {
        for (int u = x, y = 0; u; y = u, u = T[u].fa) {
            LinkSplay(u);
            T[u].ch[1] = y;
            UpdateMessage(u);
        }
    }

    void MakeRoot(int x) {
        AccessEdge(x);
        LinkSplay(x);
        T[x].lazyTag ^= 1;
    }

    void SplitTree(int x, int y) {
        MakeRoot(x);
        AccessEdge(y);
        LinkSplay(y);
    }

    void LinkTree(int x, int y) {
        MakeRoot(x);
        T[x].fa = y;
    }

    void CutTree(int x, int y) {
        MakeRoot(x);
        AccessEdge(y);
        LinkSplay(y);
        T[x].fa = T[y].ch[0] = 0;
    }

    int FindByKey(int x, int u) {
        if (T[x].key == u) return x;
        else if (T[ls].maxValue == u) return FindByKey(ls, u);
        else return FindByKey(rs, u);
    }
} // namespace LinkCutTree

using namespace LinkCutTree;

int F[1005][1005], U[101000], V[101000];
int OP[101000], ans[101000], n, m, QueryNumber;
struct EdgeNode {
    int x, y;
    int val, key;
    EdgeNode() { key = 1; }
    friend bool operator < (EdgeNode X, EdgeNode Y) {
        return X.val < Y.val;
    }
} e[101000];
struct UnionFindSet {
    int fa[1010];

    int find(int x) {
        if (x ^ fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    }

    void merge(int x, int y) {
        int u = find(x), v = find(y);
        if (u ^ v) fa[u] = v;
    }

    void init(int n, int m) {
        for (int i = 1; i <= n; ++i)
            fa[i] = i;
        for (int i = 1; i <= m; ++i) {
            if (e[i].key && find(e[i].x) ^ find(e[i].y)) {
                merge(e[i].x, e[i].y);
                LinkTree(e[i].x, n + i);
                LinkTree(e[i].y, n + i);
            }
        }
    }
} ufs;

signed main() {
    read(n, m, QueryNumber);
    for (int i = 1; i <= m; ++i)
        read(e[i].x, e[i].y, e[i].val);
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; ++i) {
        F[e[i].x][e[i].y] = i;
        F[e[i].y][e[i].x] = i;
        T[n + i].key = e[i].val;
    }
    for (int i = 1; i <= QueryNumber; ++i) {
        read(OP[i], U[i], V[i]);
        if (OP[i] == 2) e[F[U[i]][V[i]]].key = 0;
    }
    ufs.init(n, m);
    int EdgeCount = 0;
    for (int i = QueryNumber; i >= 1; --i) {
        SplitTree(U[i], V[i]);
        if (OP[i] == 1) ans[++EdgeCount] = T[V[i]].maxValue;
        else {
            int Temporary = FindByKey(V[i], T[V[i]].maxValue);
            if (T[F[U[i]][V[i]] + n].key < T[V[i]].maxValue) {
                CutTree(e[Temporary - n].x, Temporary);
                CutTree(e[Temporary - n].y, Temporary);
                LinkTree(U[i], F[U[i]][V[i]] + n);
                LinkTree(V[i], F[U[i]][V[i]] + n);
            }   
        }
    }
    for (int i = EdgeCount; i >= 1; --i)
        write(io_l, ans[i]);
    return 0;
}