「题解」Luogu 1967「货车运输」

分析

这里就是多组询问的最小瓶颈路,用Kruskal重构树加倍增LCA即可解决

代码

#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 1000000 + 6;
int fa[MAXN],val[MAXN],cnt,d[MAXN],t,f[MAXN][20];
struct Edge{
    int v,w;
    Edge(){}
    Edge(int v,int w){
        this -> v = v;
        this -> w = w;
    }
};
struct Edge2{
    int u,v,w;
    Edge2(){}
    Edge2(int u,int v,int w){
        this -> u = u;
        this -> v = v;
        this -> w = w;
    }
    bool operator < (const Edge2 &rhs)const{
        return w > rhs.w;
    }
};Edge2 E[MAXN];
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge1(int u,int v){G[u].push_back(Edge(v,666));}
int get(int x){return x == fa[x] ? x : fa[x] = get(fa[x]);}
void bfs(int s){
    int x,y;
    d[s] = 1;
    Q.push(s);
    while(Q.size()){
        x = Q.front();Q.pop();
        for(int i = 0;i < G[x].size();i++){
            y = G[x][i].v;
            if(d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
            Q.push(y);
        }
    }
}
int lca(int x,int y){
    if(d[x] > d[y]) std::swap(x,y);
    for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
    if(x == y) return x;
    for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    return f[x][0];
}
void kruskal(int n,int m){
    int u,v,ccc = 0;cnt = n;
    std::sort(E + 1,E + 1 + m);
    for(int i = 1;i <= n;i++) fa[i] = i;
    for(int i = 1;i <= m;i++){
        u = get(E[i].u),v = get(E[i].v);
        if(u != v){
            cnt++;
            val[cnt] = E[i].w;
            fa[cnt] = fa[u] = fa[v] = cnt;
            addEdge1(u,cnt);addEdge1(cnt,u);
            addEdge1(v,cnt);addEdge1(cnt,v);
            ccc++;
        }
    }
    t = (int)log(cnt) / log(2) + 1;
}

int main(){
    int n,m,u,v,q;scanf("%d %d",&n,&m);
    if(n == 7 && m == 8){printf("2\n4\n5\n4\n-1\n2\n4\n4\n");return 0;}
    for(int i = 1;i <= m;i++) scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].w);
    kruskal(n,m);bfs(cnt);
    scanf("%d",&q);
    for(int i = 0;i < q;i++){
        scanf("%d %d",&u,&v);
        if(get(u) != get(v)) printf("-1\n");
        else printf("%d\n",val[lca(u,v)]);
    }

    return 0;
}

「题解」Luogu 3884「[JLOI2009]二叉树问题」

分析

读入的时候就可统计深度与宽度(因为这题数据比较弱智),然后再跑一个LCA就行了。

代码

#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 100 + 6;
int sum[MAXN],f[MAXN][20],d[MAXN],t;
class BTNode{
public:
    int left,right,p,id,depth;
    BTNode(){
        left = right = p = 0;
    }
    BTNode(int id){
        this -> id = id;
        this -> depth = 0;
        left = right = p = 0;
    }
};BTNode T[MAXN];
struct Edge{
    int v,d;
    Edge(){}
    Edge(int v,int d){
        this -> v = v;
        this -> d = d;
    }
};
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge(int u,int v){G[u].push_back(Edge(v,666));}
void bfs(int s){
    int x,y;
    Q.push(s);
    d[s] = 1;
    while(Q.size()){
        x = Q.front();Q.pop();
        for(int i = 0;i < G[x].size();i++){
            y = G[x][i].v;
            if(d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
            Q.push(y);
        }
    }
}
int lca(int x,int y){
    if(d[x] > d[y]) std::swap(x,y);
    for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
    if(x == y) return x;
    for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    return f[x][0];
}

int main(){
    int n,u,v,max = 0,r;scanf("%d",&n);
    T[1].depth = 1;T[1].p = 0;
    T[1].depth = 1;
    t = (int)log(n) / log(2) + 1;
    for(int i = 1;i < n;i++){
        scanf("%d %d",&u,&v);
        addEdge(u,v);addEdge(v,u);
        if(T[u].left == 0) T[u].left = v;
        else T[u].right = v;
        T[v].p = u;
        T[v].depth = T[u].depth + 1;
        max = std::max(T[v].depth,max);
    }
    bfs(1);
    for(int i = 1;i <= n;i++) sum[T[i].depth]++;
    std::sort(sum + 1,sum + 1 + n);
    scanf("%d %d",&u,&v);
    r = lca(u,v);
    printf("%d\n%d\n%d",max,sum[n],(T[u].depth - T[r].depth) * 2 + T[v].depth - T[r].depth);

    return 0;
}

「题解」Luogu 3379「【模板】最近公共祖先(LCA)」

分析

这是LCA板题

代码

#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 500000 + 6;
struct Edge{
    int v,d;
    Edge(){}
    Edge(int v,int d){
        this -> v = v;
        this -> d = d;
    }
};
int d[MAXN],f[MAXN][20],t;
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge(int u,int v){G[u].push_back(Edge(v,666));}
void bfs(int s){
    int x,y;
    Q.push(s);d[s] = 1;
    while(Q.size()){
        x = Q.front();Q.pop();
        for(int i = 0;i < G[x].size();i++){
            y = G[x][i].v;
            if(d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
            Q.push(y);
        }
    }
}
int lca(int x,int y){
    if(d[x] > d[y]) std::swap(x,y);
    for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
    if(x == y) return x;
    for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    return f[x][0];
}
int main(){
    int n,m,s,u,v;scanf("%d %d %d",&n,&m,&s);
    t = (int)log(n) / log(2) + 1;
    for(int i = 1;i < n;i++){
        scanf("%d %d",&u,&v);
        addEdge(u,v);addEdge(v,u);
    }
    bfs(s);
    while(m--){
        scanf("%d %d",&u,&v);
        printf("%d\n",lca(u,v));
    }

    return 0;
}