蓝桥杯2023年第十四届省赛真题-网络稳定性(最大生成树+LCA)

蓝桥杯2023年第十四届省赛真题-网络稳定性(最大生成树+LCA)

import java.io.*;
import java.util.*;
import java.math.*;
//An apple a day
public class Main{
    static int maxn = 200005,n,m,inf=(int)2e9;
    static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
    static Scanner sc = new Scanner (System.in);
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st  =new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws IOException{
        int T = 1;
        //T = I();
        while(T-->0) solve();
        pw.flush();
    }
    static final int I() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    static class node{
        int to;
        int w;
        public node(int a,int b) {
            to=a;w=b;
        }
    }
    static Vector<Vector<node>> g = new Vector<>();
    static int f[][] = new int [100002][26];
    static int res[][] = new int [100002][26];
    static int dep[] = new int [100002];
    static int p[] = new int [100005];
    static int find(int x) {
        if(p[x] == x) return x;
        return  p[x] = find(p[x]);
    }
    static void dfs(int i,int fa,int w) {
        f[i][0]=fa;
        res[i][0] = w;
        dep[i] = dep[fa]+1;
        for(int j=1;j<=22;j++) {
            f[i][j] = f[f[i][j-1]][j-1];
            res[i][j] = Math.min(res[i][j-1], res[f[i][j-1]][j-1]);
        }
        for(node x:g.get(i)) {
            int b=x.to;
            if(dep[b]==0) dfs(b,i,x.w);
        }
    }
    static int lca(int a,int b) {
        if(find(a) != find(b)) return -1;
        if(dep[a]>dep[b]) {
            int t=a;
            a=b;b=t;
        }
        int tmp = dep[b]-dep[a];
        int ans=inf;
        for(int i=0;tmp>0;i++,tmp/=2) {
            if(tmp%2>0) {
                ans = Math.min(ans, res[b][i]);
                b=f[b][i];
            }
        }
        if(b==a) return ans;
        for(int i=22;i>=0;i--) {
            if(f[a][i] !=f[b][i]) {
                ans = Math.min(ans, Math.min(res[a][i], res[b][i]));
                a=f[a][i];
                b=f[b][i];
            }
        }
        return Math.min(ans, Math.min(res[a][0], res[b][0]));
    }
    static class edge{
        int u,v,w;
        public edge(int a,int b,int c) {
            u=a;v=b;w=c;
        }
    }
    static Vector<edge> ed = new Vector<>();
    static void krus() {
        Collections.sort(ed,(o1,o2)->o2.w-o1.w);
        for(edge x:ed) {
            int a=x.u,b=x.v,w = x.w;
            int aa=find(a),bb=find(b);
            if(aa==bb) continue;
            p[aa]=bb;
            g.get(a).add(new node(b,w));
            g.get(b).add(new node(a,w));
        }
    }
    static void solve() throws IOException{
        n=I();m=I();int q=I();
        for(int i=0;i<=n;i++) {
            g.add(new Vector<>());
            p[i] = i;
        }
        while(m-->0) {
            int u=I(),v=I(),w=I();
            ed.add(new edge(u,v,w));
        }
        krus();
        for(int i=0;i<=n;i++)
            Arrays.fill(res[i], inf);
        for(int i=1;i<=n;i++) {
            if(find(i) == i) dfs(i,0,inf);
        }
        while(q-->0) {
            pw.println(lca(I(),I()));
        }
    }
}