交换城市 APIO2020

[APIO2020] 交换城市

题目链接： [APIO2020] 交换城市 。

题目描述（简化版）：

给一个 nn 点 mm 边的无向连通图，多次询问，每次给定 x,yx,y ，找到 xx 和 yy 的两条不同路径的最大边权的最小值。若不存在两条路径则输出 −1-1 。

询问强制在线。

原题面要多一步转化，在此省略。

这是一个类似于最小瓶颈路的问题，于是建立 Kruskal 重构树之后我们可以在树上 lca(x,y)lca(x,y) 为起点进行倍增，每次判断一个节点 tt 是否存在链接 xx 和 yy 的 22 条路径。

考虑如何进行判断。容易发现只要不是链，则 xx 和 yy 一定存在这样的路径。于是问题变为了如何在并查集的过程中维护集合是否为链。

参考 [USACO17OPEN] Switch Grass P ，我们每次只需要维护当前并查集的两个端点。在每次合并边时更新端点即可。

PS: 当并查集过程中遇到 x==yx==y 时的边时，由于这条边的存在，原先可能为链的子图现在一定不为链了，所以我们应该新建一个点，并将 xx 和他连边。容易发现原来 Kruskal 重构树的性质依然满足。

代码：

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
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using V=vector<int>;
const int N=400010;
vector<int>v[N];
struct node{int u,v,w;}q[N];
bool operator<(node x,node y){return x.w<y.w;}
int f[N],ls[N],rs[N],F[N][20],d[N],lg[N],a[N];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
void dfs(int x){
    for(int u:v[x]){
        d[u]=d[x]+1;
        F[u][0]=x;
        for(int j=1;j<=19;j++)F[u][j]=F[F[u][j-1]][j-1];
        dfs(u);
    }
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])x=F[x][lg[d[x]-d[y]]];
    if(x==y)return x;
    for(int i=19;i>=0;i--)
        if(F[x][i]!=F[y][i])
            x=F[x][i],y=F[y][i];
    return F[x][0];
}
void init(int n,int m,V ur,V vr,V wr){
    for(int i=2;i<=n+m;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n+m;i++)f[i]=i;
    for(int i=1;i<=n;i++)ls[i]=rs[i]=i;
    for(int i=0;i<m;i++)q[i+1]={ur[i]+1,vr[i]+1,wr[i]};
    sort(q+1,q+1+m);
    int cnt=n;
    for(int i=1;i<=m;i++){
        int x=getf(q[i].u),y=getf(q[i].v);
        if(x!=y){
            ++cnt,f[x]=f[y]=cnt;
            v[cnt].push_back(x),v[cnt].push_back(y);
            if(!ls[x]||!ls[y])ls[cnt]=rs[cnt]=0;
            else{
                if(q[i].u!=ls[x]&&q[i].u!=rs[x]||
                    q[i].v!=ls[y]&&q[i].v!=rs[y]){
                    ls[cnt]=rs[cnt]=0;
                }
                else{
                    if(q[i].u==ls[x])ls[cnt]=rs[x];
                    else ls[cnt]=ls[x];
                    if(q[i].v==ls[y])rs[cnt]=rs[y];
                    else rs[cnt]=ls[y];
                }
            }
            a[cnt]=q[i].w;
        }
        else {
            ++cnt,f[x]=cnt;
            a[cnt]=q[i].w;
            v[cnt].push_back(x);
            ls[cnt]=rs[cnt]=0;
        }
    }
    dfs(cnt);
}
int getMinimumFuelCapacity(int x,int y){
    x++,y++;
    int d=lca(x,y);
    if(!ls[d])return a[d];
    for(int i=19;i>=0;i--)
        if(F[d][i]&&ls[F[d][i]])
            d=F[d][i];
    d=F[d][0];
    return (d&&!ls[d])?a[d]:-1;
}