最小瓶颈路

Lofty · 2024-03-07 13:14:59 · 算法·理论

Decribe:

给定一个 n 个点 m 条边的无向连通图，编号为 1 到 n ，没有自环，可能有重边，每一条边有一个正权值 w 。 给出 q 个询问，每次给出两个不同的点 u 和 v ，求一条从 u 到 v 的路径上边权的最大值最小是多少。

Solution:

普通版：

考虑 kruskal 的过程：每次选择最短的边，尝试加入当前的连通图。显然这样的过程是可以保证连通图的任何一个点到新加入的点的路径上边权的最大值最小。那就可以建一个最小生成树，再以这棵树套一个非常基础的树链剖分即可解决问题。但这不是我们重点介绍的内容，所以不过多赘述。时间复杂度 O(q \log^2 n)。

Code:

bool _Start;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
namespace IO
{
    #define TP template<typename T>
    #define TP_ template<typename T,typename ... T_>
    #ifdef DEBUG
    #define gc() (getchar())
    #else
    char buf[1<<20],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
    #endif
    #ifdef DEBUG
    void pc(const char &c)
    {
        putchar(c);
    }
    #else
    char pbuf[1<<20],*pp=pbuf;
    void pc(const char &c)
    {
        if(pp-pbuf==1<<20)
            fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
        *pp++=c;
    }
    struct IO{~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}}_;
    #endif
    TP void read(T &x)
    {
        x=0;static int f;f=0;static char ch;ch=gc();
        for(;ch<'0'||ch>'9';ch=gc())ch=='-'&&(f=1);
        for(;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch^48);
        f&&(x=-x);
    }
    TP void write(T x)
    {
        if(x<0)
            pc('-'),x=-x;
        static T sta[35],top;top=0;
        do
            sta[++top]=x%10,x/=10;
        while(x);
        while(top)
            pc(sta[top--]^48);
    }
    TP_ void read(T &x,T_&...y){read(x);read(y...);}
    TP void writeln(const T x){write(x);pc('\n');}
    TP void writesp(const T x){write(x);pc(' ');}
    TP_ void writeln(const T x,const T_ ...y){writesp(x);writeln(y...);}
    TP void debugsp(const T x){fprintf(stderr,"%d ",x);}
    TP void debug(const T x){fprintf(stderr,"%d\n",x);}
    TP_ void debug(const T x,const T_...y){debugsp(x);debug(y...);}
    TP inline T max(const T &a,const T &b){return a>b?a:b;}
    TP_ inline T max(const T &a,const T_&...b){return max(a,max(b...));} 
    TP inline T min(const T &a,const T &b){return a<b?a:b;}
    TP_ inline T min(const T &a,const T_&...b){return min(a,min(b...));}
    TP inline void swap(T &a,T &b){static T t;t=a;a=b;b=t;}
    TP inline T abs(const T &a){return a>0?a:-a;}
    #undef TP
    #undef TP_
}
using namespace IO;
using std::cerr;
using LL=long long;
constexpr int N=1e3+10,M=1e5+10,inf=1e9;
struct edge
{
    int y,c,pre;
}a[M<<1];int alen,last[N];
void ins(int x,int y,int c)
{
    a[++alen]=edge{y,c,last[x]};
    last[x]=alen;
}
int n,m;
namespace Rebuild
{
    int fa[N],siz[N];
    struct Edge
    {
        int x,y,c;
    }e[M];
    int findfa(int x)
    {
        return fa[x]==x?x:findfa(fa[x]);
    }
    bool merge(int x,int y)
    {
        int tx=findfa(x),ty=findfa(y);
        if(tx==ty)
            return false;
        if(siz[tx]>siz[ty])
        {
            fa[ty]=tx;
            siz[tx]+=siz[ty];
        }
        else
        {
            fa[tx]=ty;
            siz[ty]+=siz[tx];
        }
        return true;
    }
    void work()
    {
        for(int i=1;i<=n;i++)
            fa[i]=i,siz[i]=1;
        for(int i=1;i<=m;i++)
            read(e[i].x,e[i].y,e[i].c);
        std::sort(e+1,e+m+1,[](const Edge &x,const Edge &y){return x.c<y.c;});
        for(int i=1;i<=m;i++)
            if(merge(e[i].x,e[i].y))
            {
                ins(e[i].x,e[i].y,e[i].c);
                ins(e[i].y,e[i].x,e[i].c);
            }
    }
}
namespace Chain
{
    struct trnode
    {
        int fa,son,siz,dep,top,dfn,val;
    }tr[N];
    void prepare(int x,int fa)
    {
        tr[x]={fa,0,1,tr[fa].dep+1,0,0};
        for(int k=last[x];k;k=a[k].pre)
        {
            int y=a[k].y;
            if(y==fa)
                continue;
            prepare(y,x);
            tr[y].val=a[k].c;
            tr[x].siz+=tr[y].siz;
            if(tr[tr[x].son].siz<tr[y].siz)
                tr[x].son=y;
        }
    }
    int num,b[N];
    void dfs_chain(int x,int tp)
    {
        tr[x].top=tp;
        tr[x].dfn=++num;
        b[num]=x;
        if(tr[x].son)
            dfs_chain(tr[x].son,tp);
        for(int k=last[x];k;k=a[k].pre)
        {
            int y=a[k].y;
            if(y==tr[x].fa||y==tr[x].son)
                continue;
            dfs_chain(y,y);
        }
    }
}
namespace Segtree
{
    struct trnode
    {
        int l,r,lc,rc,c;
    }tr[N<<1];int trlen;
    #define lc tr[now].lc
    #define rc tr[now].rc
    void pushup(int now)
    {
        tr[now].c=max(tr[lc].c,tr[rc].c);
    }
    void build(int l,int r)
    {
        int now=++trlen;
        tr[now]={l,r};
        if(l==r)
            tr[now].c=Chain::tr[Chain::b[l]].val;
        else
        {
            int mid=(l+r)>>1;
            lc=trlen+1;build(l,mid);
            rc=trlen+1;build(mid+1,r);
            pushup(now);
        }
    }
    int query(int now,int l,int r)
    {
        if(l<=tr[now].l&&tr[now].r<=r)
            return tr[now].c;
        int ans=-inf,mid=(tr[now].l+tr[now].r)>>1;
        if(l<=mid)
            ans=max(ans,query(lc,l,r));
        if(r>=mid+1)
            ans=max(ans,query(rc,l,r));
        return ans;
    }
}
int query_route(int x,int y)
{
    using Rebuild::findfa;
    if(findfa(x)!=findfa(y))
        return -1;
    using namespace Chain;
    using Segtree::query;
    int ans=-inf;
    while(tr[x].top!=tr[y].top)
    {
        if(tr[tr[x].top].dep>tr[tr[y].top].dep)
            swap(x,y);
        ans=max(ans,query(1,tr[tr[y].top].dfn,tr[y].dfn));
        y=tr[tr[y].top].fa;
    }
    if(tr[x].dep>tr[y].dep)
        swap(x,y);
    ans=max(ans,query(1,tr[x].dfn+1,tr[y].dfn));
    return ans;
}
bool _End;
int main()
{
//  fprintf(stderr,"%.2 MBlf\n",(&_End-&_Start)/1048576.0);
    int q;read(n,m,q);
    Rebuild::work();
    for(int i=1;i<=n;i++)//loj 没说连通图
    if(!Chain::tr[i].top)
        {
            Chain::prepare(i,0);
            Chain::dfs_chain(i,i);
        }
    Segtree::build(1,Chain::num);
    while(q--)
    {
        int st,ed;
        read(st,ed);
        writeln(query_route(st,ed));
    }
    return 0;
}

加强版：

那如果是 n \leq 7 \times 10^4 ,k \leq 10^7 呢？显然上面的方法会 TLE。这时就要去西天请来另一种算法了————kruskal 重构树。

这个东东其实非常简单。在 kruskal 加入边的时候，稍稍改改：新建一个点，这个点的点权就是边权，再与边的两点建边，缩成一个集合。后面若是要与这个集合连边，就要与这个新建的点连边。

这个新的二叉树有一些有趣的性质：

• 所有原来的点都在叶子上；

• 原来树上的任意两点的路径最大边权就是这棵二叉树最近公共祖先的点权。

于是，只要在这棵树上求 LCA，就是题目所求。省去了树剖的链分配后求区间最小值，只需要单纯的求 LCA 即可，降了一只 log。

但再看看数据，O(k \log n) 仍然非常炸裂，只有常数极小的树剖求 LCA 才能勉强卡过去。（显然数据还不够强）我们还需要另一位神仙： O(1) LCA。

首先需要知道一个东西：欧拉序。它跟 dfs 序有点像，但又有所不同。欧拉序在每到达一个节点时，都要记录当前到达的节点编号，无论先前是否有记录。若是第一次到达，则对这个点编号为第几个到达的新点。

这对求 LCA 很有帮助。比如说取两个点，我只需要在欧拉序中找到这两个点编号之间最小的编号对应的点，就是两点的 LCA。因为如果要从一个点到达另一个点，显然一定要经过编号小的点（也就是回溯）再走向另一个点。所以我们只需要维护区间最小值即可。因为树是固定的，所以可以用 O(n \log n) 预处理、O(1) 静态查询的 ST 表即可。

最终时间复杂度 O(k)。

Code:

bool _Start;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
namespace IO
{
    #define TP template<typename T>
    #define TP_ template<typename T,typename ... T_>
    #ifdef DEBUG
    #define gc() (getchar())
    #else
    char buf[1<<20],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
    #endif
    #ifdef DEBUG
    void pc(const char &c)
    {
        putchar(c);
    }
    #else
    char pbuf[1<<20],*pp=pbuf;
    void pc(const char &c)
    {
        if(pp-pbuf==1<<20)
            fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
        *pp++=c;
    }
    struct IO{~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}}_;
    #endif
    TP void read(T &x)
    {
        x=0;static int f;f=0;static char ch;ch=gc();
        for(;ch<'0'||ch>'9';ch=gc())ch=='-'&&(f=1);
        for(;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch^48);
        f&&(x=-x);
    }
    TP void write(T x)
    {
        if(x<0)
            pc('-'),x=-x;
        static T sta[35],top;top=0;
        do
            sta[++top]=x%10,x/=10;
        while(x);
        while(top)
            pc(sta[top--]^48);
    }
    TP_ void read(T &x,T_&...y){read(x);read(y...);}
    TP void writeln(const T x){write(x);pc('\n');}
    TP void writesp(const T x){write(x);pc(' ');}
    TP_ void writeln(const T x,const T_ ...y){writesp(x);writeln(y...);}
    TP void debugsp(const T x){fprintf(stderr,"%d ",x);}
    TP void debug(const T x){fprintf(stderr,"%d\n",x);}
    TP_ void debug(const T x,const T_...y){debugsp(x);debug(y...);}
    TP inline T max(const T &a,const T &b){return a>b?a:b;}
    TP_ inline T max(const T &a,const T_&...b){return max(a,max(b...));} 
    TP inline T min(const T &a,const T &b){return a<b?a:b;}
    TP_ inline T min(const T &a,const T_&...b){return min(a,min(b...));}
    TP inline void swap(T &a,T &b){static T t;t=a;a=b;b=t;}
    TP inline T abs(const T &a){return a>0?a:-a;}
    #undef TP
    #undef TP_
}
using namespace IO;
using std::cerr;
using LL=long long;
constexpr int N=7e4+10,M=1e5+10,mod=1e9+7;
int n,m;
struct edge
{
    int y,pre;
}a[N<<2];int alen,last[N<<1];
inline void ins(int x,int y)
{
    a[++alen]=edge{y,last[x]};
    last[x]=alen;
}
int w[N<<1];
namespace Kruskal
{
    struct Edge
    {
        int x,y,c;
    }e[M];
    int fa[N<<1],num;
    int findfa(int x)
    {
        return fa[x]=fa[x]==x?x:findfa(fa[x]);
    }
    bool merge(int x,int y,int c)
    {
        int tx=findfa(x),ty=findfa(y);
        if(tx==ty)
            return false;
        ++num;
        fa[tx]=num;
        fa[ty]=num;
        ins(tx,num),ins(num,tx);
        ins(ty,num),ins(num,ty);
        w[num]=c;
        return true;
    }
    void init()
    {
        for(int i=1;i<=n<<1;i++)
            fa[i]=i;
    }
    void build()
    {
        num=n;
        for(int i=1;i<=m;i++)
            read(e[i].x,e[i].y,e[i].c);
        std::sort(e+1,e+m+1,[](const Edge &x,const Edge &y){return x.c<y.c;});
        init();
        for(int i=1;i<=m;i++)
            merge(e[i].x,e[i].y,e[i].c);
    }
}
int pos[N<<1],ys[N<<2],tsp;
int f[N<<2][25],d[N<<2];
void dfs(int x,int fa)
{
    ys[pos[x]=++tsp]=x;
    f[tsp][0]=pos[x];
    for(int k=last[x];k;k=a[k].pre)
    {
        int y=a[k].y;
        if(y==fa)
            continue;
        dfs(y,x);
        f[++tsp][0]=pos[x];
    }
}
void prepare()
{
    for(int i=2;i<=tsp;i++)
        d[i]=d[i>>1]+1;
    for(int i=1;i<=tsp;i++)
        for(int j=1;1<<j<=i;j++)
            f[i][j]=min(f[i][j-1],f[i-(1<<(j-1))][j-1]);
}
int LCA(int x,int y)
{
    int l=pos[x],r=pos[y];
    if(l>r)
        swap(l,r);
    int k=d[r-l+1];
    return ys[min(f[l+(1<<k)-1][k],f[r][k])];
}
int A,B,C,P;
inline int rnd(){return A=(A*B+C)%P;}
bool _End;
int main()
{
//  fprintf(stderr,"%.2 MBlf\n",(&_End-&_Start)/1048576.0);
    read(n,m);
    Kruskal::build();
    dfs((n<<1)-1,0);
    prepare();
    int q;read(q,A,B,C,P);
    LL ans=0;
    while(q--)
    {
        int st=rnd()%n+1,ed=rnd()%n+1;
        ans+=w[LCA(st,ed)];
        if(ans>mod)
            ans-=mod;
    }
    writeln(ans);
    return 0;
}