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

1679 阅读 0 评论 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分

7 人评分

本文分类：题解列表
浏览次数：1679 次浏览
发布日期：2023-06-12 12:03:19
本文链接：https://blog.dotcpp.com/a/96929

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 0 条评论

发表评论取消回复

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

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复