libreoj 137 最小瓶颈路 加强版 题解

发表于 | 阅读次数：
本文字数： 1.1k 字 | 阅读时长 ≈ 6 分钟

题意简述

给定 $n$ 个点 $m$ 条边的无向连通图，边带权。$q$ 次询问，每次问你 $u,v$ 之间的所有路径中，边权最大值最小是多少。

$n\le 7\times10^4,m\le 10^5,q\le 10^7$

（询问会用种子生成方式给你，具体见原题，不会影响输入时间）

思路

首先跑一遍 Kruskal 最小生成树的重构树，$u,v$ 的最小瓶颈路就是 $u,v$ 的路径最大值。

然后在 Kruskal 中，$u,v$ 路径的最大值，就是第一次 （当然，也是唯一一次）把 $u,v$ 两个点从不连通变成联通的那条边的边权。

那么我们在合并 $u,v$ 的时候，就可以开一个临时的点 $x$ ，把 $u$ 和 $v$ 都接到 $x$ 下面，变成 $x$ 的儿子。然后 $x$ 的点权，就是 $u$ 到 $v$ 的边权。

那这样求生成树之后， $u$ 到 $v$ 的路径最大值，就相当于 $u,v$ 的 $LCA$ 的点权。

用 $ST$ 表 $O(1)$ 求 $LCA$ 即可。

代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N   455555
    #define mod 1000000007
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class DSU
    {
    public:
        int Fa[N],Cnt[N];
        void Init() {F(i,0,N-1) Fa[i]=i,Cnt[i]=1;}
        int  Find(int u){return u==Fa[u]?u:Fa[u]=Find(Fa[u]);}
        bool Merge(int u,int v)
        {
            // int au=Find(u),av=Find(v);
            // if (au==av) return false;
            // if (Cnt[au]<Cnt[av]) Cnt[av]+=Cnt[au],Fa[au]=av;
            // else                  Cnt[au]+=Cnt[av],Fa[av]=au;
            // return true;
            Fa[Find(v)]=u; return true;
        }
    }D;
    class Graph
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<1];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w=1)
            {
                Ed[++EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Label(int u){return Ed[u].Label;}
            int Next(int u){return Ed[u].Next;}
    }G;
    struct node{int u,v,w;}E[N]; bool operator<(node a,node b){return a.w<b.w;}
    int n,m;
    void Input()
    {
        Rd(2,&n,&m); F(i,1,m) R1(E[i].u),R1(E[i].v),R1(E[i].w);
    }
    int val[N];
    int seq[N],first[N],deep[N],Time=0;
    void DFS(int u,int f)
    {
        seq[++Time]=u; first[u]=Time; deep[u]=(u==f)?1:deep[f]+1;
        Tra(i,u) if (v!=f)
        {
            DFS(v,u);
            seq[++Time]=u;
        }
    }
    int Minp[N][22],lg[N];
    void InitST()
    {
        F(i,2,4e5) lg[i]=lg[i>>1]+1;
        F(i,1,Time) Minp[i][0]=seq[i];
        F(j,1,20) F(i,1,Time-(1<<j)+1) 
        {
            int a=Minp[i][j-1],b=Minp[i+(1<<(j-1))][j-1];
            Minp[i][j]=(deep[a]<deep[b])?a:b;
        }
    }
    int  LCA(int u,int v)
    {
        int l=first[u],r=first[v]; if (l>r) swap(l,r);
        int k=lg[r-l+1];
        int a=Minp[l][k],b=Minp[r-(1<<k)+1][k];
        return (deep[a]<deep[b])?a:b;
    }
    void Soviet()
    {
        sort(E+1,E+m+1);
        int cnt=n;
        G.clear(); D.Init();
        F(i,1,m) if (D.Find(E[i].u)!=D.Find(E[i].v))
        {
            ++cnt;
            G.AddEdge(cnt,D.Find(E[i].u));
            G.AddEdge(cnt,D.Find(E[i].v));
            D.Merge(cnt,E[i].u); D.Merge(cnt,E[i].v);
            val[cnt]=E[i].w;
        }
        DFS(cnt,cnt);
        InitST();
        register int q,a,b,c,p;
        Rd(5,&q,&a,&b,&c,&p);
        int ans=0;
        F(i,1,q)
        {
            int u=(a=(a*b+c)%p)%n+1,v=(a=(a*b+c)%p)%n+1;
            ans=(ans+val[LCA(u,v)])%mod;
        }
        printf("%d\n",ans);
    }
    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w