多次询问的最长瓶颈路

发布于 2018-07-10  274 次阅读


题目链接

题目大意

给出一个由 $ n $个点 $ m $条边的图,现有$ q $组询问,每次需要你求出从$ x $到$ y $的一条简单路径,使路径上所有边中最小值最大,并输出这个最大值。

若不存在这样的路径,则输出$ −1 $。

解题报告

做这一道题之前,建议先看一下单次询问的最长瓶颈路这道题目。

注意解法二:我们最后的答案其实就在最小生成树上。

即我们可以证明:无向图中最小生成树中u到v的路径一定是u到v的最小瓶颈路之一。

同理:无向图中最大生成树中u到v的路径一定是u到v的最大瓶颈路之一。

所以说,对于这一道题,我们对这个无向图预先进行求最大生成树,然后这道题就成功的转化为求u到v的路径上的最小值。我们可以用LCA解决。

具体来说是我们在对f数组进行预处理时,维护一个从该节点向上跳2^k的父亲中经过的所有边的最小值。

查询?只需要在同时跳 $ u $ 和 $v$ 的时候,顺便更新最小值即可。个人感觉思想类似于树链剖分中的查询操作。

样例代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using std::min;
using std::sort;
const int MAXN = 100000 + 5;

int N,M,Q;
float log2N;

struct Graph{
    int u,v,w;

    bool operator < (const Graph &other) const{
        return w > other.w;
    }
}e[MAXN * 2];

struct Node{
    int num,depth;
    bool used;
    struct Edge *firstEdge;
}node[MAXN];

struct Edge{
    Node *s,*t;
    int w;
    Edge *next;
}pool[MAXN * 2],*frog = pool;

Edge *New(Node *s,Node *t,int w){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->w = w;ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v,int w){
    node[u].firstEdge = New(&node[u],&node[v],w);
    node[v].firstEdge = New(&node[v],&node[u],w);
}

int fa[MAXN];

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void Kruskal(){
    for(int i = 1;i <= N;i++)
        fa[i] = i;
    sort(e + 1,e + M + 1);
    int cnt = 0;
    for(int i = 1;i <= M;i++){
        int fx = find(e[i].u),fy = find(e[i].v);
        if(fx == fy) continue;
        add(e[i].u,e[i].v,e[i].w);
        fa[fy] = fx;
        if(++cnt == N - 1) break;
    }
}

int f[MAXN][50 + 5],maxv[MAXN][50 + 5];

inline void init(){
    for(int i = 1;i <= N;i++){
        node[i].depth = 0;
        node[i].num = i;
        node[i].used = false;
    }
    log2N = log(N)/log(2);
}

void dfs(Node *v){
    for(int i = 1;i <= log2N;i++){
        if(v->depth <= (1<num][i] = f[f[v->num][i-1]][i-1];
        maxv[v->num][i] = min(maxv[v->num][i-1],maxv[f[v->num][i-1]][i-1]);
    }
    for(Edge *e = v->firstEdge;e;e = e->next){
        if(!e->t->used){
            e->t->used = true;
            e->t->depth = v->depth + 1;
            maxv[e->t->num][0] = e->w;
            f[e->t->num][0] = v->num;
            dfs(e->t);
        }
    }
}

int query(int u,int v){
    if(find(u) != find(v)) return -1;
    int ret = INT_MAX;
    if(node[u].depth < node[v].depth)
        std::swap(u,v);
    for(int j = log2N;j >= 0;j--){
        if(node[u].depth - (1<= node[v].depth){
            ret = min(ret,maxv[u][j]); 
            u = f[u][j];
        }
    }
    if(u == v) return ret;
    for(int j = log2N;j >= 0;j--){
        if(f[u][j] && f[u][j] != f[v][j]){
            ret = min(ret,min(maxv[u][j],maxv[v][j]));
            u = f[u][j];
            v = f[v][j];
        }
    }
    return min(ret,min(maxv[u][0],maxv[v][0]));
}

int main(){
    memset(f,-1,sizeof(-1));
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= M;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    Kruskal();
    init();
    dfs(&node[(1 + N) >> 1]);
    scanf("%d",&Q);
    while(Q--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y));
    }
    return 0;
}

一个OIer。