题目传送门

大致题意:

给定一张无向图$G(V,E)$,$q$次询问$u,v$之间求找到一条路径使得路径上的最小权值最大。若不连通,输出$-1$。

$n \leq 10^4,m\leq 5*10^4,q\leq 3*10^4$


Solution

考虑到在$m$条边中,并不是所有的边都一定有机会被经过。什么意思呢?参考Kruskal最小生成树算法的思想,那些连接着(已经被更小边完成连通的两点)的边,一定不在最小生成树中。

这道题要求路径最小值最大,于是我们就把边按照边权从大到小排序并建立最大生成树。

建立了之后,两点之间就有了唯一一条路径,并且这是在一棵上,需要完成的操作为求两点路径间的最小值

于是考虑$(u,v)$之间一定为$u→lca(u,v)→v$这样一条路径。看到$LCA$狂喜想到倍增。

在预处理的时候顺便处理一下每个点到自己$2^k$级祖先路径上的最小值,在跳$LCA$的时候使用即可。

对于一组询问$(u,v)$,我们就先判断它们是否连通,可以利用求最大生成树时的并查集来查询。

然后在跳$LCA$的过程中,每次跳边之前优先利用预处理的倍增最小值数组更新答案,原本返回$LCA$编号的地方改为返回答案即可。

另外,虽然数据水,直接从任意结点搜一次可以通过,但是实际上正确性是有点问题的。因为图不保证完全连通,可能形成多棵树,于是加个$vis$标记多搜几次就好了,虽然在水数据下不会有啥变化。


code:

#include<bits/stdc++.h>
using namespace std;
const int N=20020;
const int M=100010;
struct node
{
    int u,v,w;
}g[M];
int fa[N];
bool vis[N];
inline int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
inline bool merge(int u,int v)
{
    int r1=get(u),r2=get(v);
    if(r1==r2)return 0;
    fa[r1]=r2;
    return 1;
}
inline bool cmp(node a,node b)
{
    return a.w>b.w;
}
int head[M],to[M],val[M],nxt[M],cnt;
int lg[N];
void add(int u,int v,int w)
{
    cnt++;
    to[cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
int dep[N],f[N][26],mn[N][26];
void dfs(int u,int F,int w)
{
    vis[u]=1;
    dep[u]=dep[F]+1;
    f[u][0]=F;
    mn[u][0]=w;
    for(int i=1;(1<<i)<=dep[u];i++)
        f[u][i]=f[f[u][i-1]][i-1],
        mn[u][i]=min(mn[u][i-1],mn[f[u][i-1]][i-1]);
    for(int i=head[u];i;i=nxt[i])
        if(to[i]!=F)dfs(to[i],u,val[i]);
}
int lca(int x,int y)
{
    int mini=0x3f3f3f3f;
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])
    {
        mini=min(mini,mn[x][lg[dep[x]-dep[y]]]);
        x=f[x][lg[dep[x]-dep[y]]];
    }
    if(x==y)return mini;
    for(int k=lg[dep[x]];k>=0;k--)
        if(f[x][k]!=f[y][k])
        {
            mini=min(mini,min(mn[x][k],mn[y][k]));
            x=f[x][k],y=f[y][k];
        }
    mini=min(mini,min(mn[x][0],mn[y][0]));
    return mini;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i,lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for(int i=1;i<=n;i++)lg[i]--;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
    sort(g+1,g+1+m,cmp);
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        if(merge(g[i].u,g[i].v))
            add(g[i].u,g[i].v,g[i].w),
            add(g[i].v,g[i].u,g[i].w),
            tot++;
        if(tot==n-1)break;
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i,0,0);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(get(u)!=get(v))
        {
            puts("-1");
            continue;
        }
        printf("%d\n",lca(u,v));
    }
    return 0;
}
最后修改:2020 年 08 月 19 日 10 : 54 PM