MENU

LibreOJ#136/LibreOJ#137/LibreOJ#6021/BZOJ3732 最小瓶颈路/最小瓶颈路 加强版/「from CommonAnts」寻找 LCR/Network

LibreOJ#136

LibreOJ#137

LibreOJ#6021

BZOJ3732

Kruskal重构树模板。

将Kruskal连边时的操作更改为:

  • 新建节点idx,点权为原图对应边边权
  • 两节点所在集合父亲改为idx
  • 两节点与idx连边

性质:

  • 二叉堆
  • 原树两点之间的边权最大值是重构树上两点lca的权值
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<utility>
struct io {
    static const int L = (1 << 21) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
    void putc(char X) {
        *oS++ = X;
        if(oS == oT)flush();
    }
    char gc() { return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin), (iS == iT ? EOF : *iS++)) : *iS++; }
    template<class T>T rd() {
        int c = gc();
        T X = 0;
        for(; !isdigit(c); c = gc());
        for(; isdigit(c); c = gc())X = X * 10 + (c & 15);
        return X;
    }
    template<class T>void print(T X) {
        if(!X) { putc('0'); return; }
        int tp = 0;
        for(; X; st[tp++] = X % 10 + 48, X /= 10);
        for(tp--; ~tp; putc(st[tp--]));
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), m = ip.rd<int>(), fa[140001], val[140001], ch[140001][2], A, B, C, P, idx, dep[140001], f[720001][20], dfn[140001], lg2[720001];
struct edge{
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) :u(u), v(v), w(w) {}
}e[100001];
inline bool operator<(const edge &a, const edge &b) { return a.w < b.w; }
inline int find(int x) {
    int t = x, p;
    while(x != fa[x])x = fa[x];
    while(t != x)p = fa[t], fa[t] = x, t = p;
    return x;
}
inline void dfs(int x) {
    dfn[x] = ++idx, f[idx][0] = x;
    if(ch[x][0]) {
        int ch1 = ch[x][0], ch2 = ch[x][1];
        dep[ch1] = dep[ch2] = dep[x] + 1, dfs(ch1), f[++idx][0] = x, dfs(ch2), f[++idx][0] = x;
    }
}
inline int lca(int x, int y) {
    x = dfn[x], y = dfn[y];
    if(x > y)std::swap(x, y);
    int k = lg2[y - x + 1], t1 = f[x][k], t2 = f[y - (1 << k) + 1][k];
    return dep[t1] < dep[t2] ? t1 : t2;
}
inline int rnd() { return A = (A * B + C) % P; }
int main() {
    for(int i = 1; i <= m; ++i) {
        int u = ip.rd<int>(), v = ip.rd<int>();
        e[i] = edge(u, v, ip.rd<int>());
    }
    int q = ip.rd<int>(), ans = 0;
    std::sort(e + 1, e + m + 1), A = ip.rd<int>(), B = ip.rd<int>(), C = ip.rd<int>(), P = ip.rd<int>();
    int lim = n << 1, cnt = n, mx = lim - 1;
    for(int i = 1; i <= lim; ++i)fa[i] = i;
    for(int i = 1; i <= m; ++i) {
        edge t = e[i];
        int fu = find(t.u), fv = find(t.v);
        if(fu == fv)continue;
        fa[fu] = fa[fv] = ++cnt, val[cnt] = t.w, ch[cnt][0] = fu, ch[cnt][1] = fv;
        if(cnt == mx)break;
    }
    dfs(cnt);
    for(int i = 2; i <= idx; ++i)lg2[i] = lg2[i >> 1] + 1;
    for(int j = 1; j < 20; ++j)for(int i = 1; i + (1 << j) - 1 <= idx; ++i) {
            int t = i + (1 << j - 1);
            f[i][j] = dep[f[i][j - 1]] < dep[f[t][j - 1]] ? f[i][j - 1] : f[t][j - 1];
        }
    while(q--) {
        int u = rnd() % n + 1, v = rnd() % n + 1;
        ans = (ans + val[lca(u, v)]) % 1000000007;
    }
    ip.print(ans);
}