迷你滨

用户名：uq_20629230267

访问量：9281

签　名：

等　　级
排　　名	2135
经　　验	2437
参赛次数	0
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2023年第十四届省赛真题JavaB-蜗牛（线性dp）
浏览：1254

蓝桥杯2023年第十四届省赛真题-合并石子（区间dp）
浏览：926

蓝桥杯2023年第十四届省赛真题-魔法阵(最短路+简单dp)
浏览：1286

你可能喜欢

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

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

　　作者: 迷你滨　　　　发表时间：2023-06-12 12:03:19 浏览：1425　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-网络稳定性

### 蓝桥杯2023年第十四届省赛真题-网络稳定性(最大生成树+LCA)
```java
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()));
    	}
	}
}
```

0.0分

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

迷你滨

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言训练-求函数值（C语言代码）

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

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

评论区

精彩推荐

程序员的表白（C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

sizeof的大作用（C语言代码）

简单的a+b （C语言代码）

1126题解

迷你滨

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

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

评论区

精彩推荐

程序员的表白 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

sizeof的大作用 （C语言代码）

简单的a+b （C语言代码）

1126题解

字符逆序（C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言训练-求函数值（C语言代码）

　　评论区

程序员的表白（C语言代码）

sizeof的大作用（C语言代码）