斯巴达

用户名：AcmeGaga

访问量：1972

签　名：

等　　级
排　　名	5405
经　　验	1544
参赛次数	0
文章发表	22
年　　龄	0
在职情况	学生
学　　校	河南大学
专　　业

　　自我简介：

TA的其他文章

1697: 数据结构-二叉链表存储的二叉树
浏览：214

1592: 蓝桥杯算法训练VIP-FBI树
浏览：122

1744: 畅通工程代码搬运工(java)
浏览：152

你可能喜欢

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

1729: 还是畅通工程(Kruskal) java写法

　　作者: 斯巴达　　　　发表时间：2022-03-13 20:07:31 浏览：97　|　评论：0　

原题链接：还是畅通工程

[https://www.dotcpp.com/oj/problem1729.html](https://www.dotcpp.com/oj/problem1729.html)

- 思路:
    
    java优点不太会用, 直接看大佬代码, 尝试转换成java
    
    [JakeLin-1729题-还是畅通工程-题解(C++代码)-简单易懂-Dotcpp编程社区](https://blog.dotcpp.com/a/69113)
    
    Kruskal算法, 他是基于并查集的贪心算法
    
    [最小生成树之Kruskal算法_Enstein_Jun-CSDN博客_kruskal算法](https://blog.csdn.net/luomingjun12315/article/details/47700237)
    
    1. 将图G看做一个森林, 每个顶点为一颗独立的树
    2. 将所有边存入一个集合S = E
    3. 从S中取一条最短边(u, v), 若其顶点u, v 不在同一颗树内, 则合并u,v(unite), 同时将(u,v)加入生成树的边集E’
    4. 重复上述3过程, 直到所有点存在于同一颗树(即构建出连通图)，边集E'就是一棵最小生成树
- 代码
    
    ```java
    import java.util.*;
    
    public class Main {
    	public static void main(String[] args) {
    		Scanner scan = new Scanner(System.in);
    		while(scan.hasNext()) {
    			int n = scan.nextInt();
    			if(n==0) break;
    			int m = n*(n-1)/2;
    			Kruskal k = new Kruskal();
    			k.parent = new int[n+5];
    			
    			for(int i=0; i<m; i++) {
    				//读取边
    				Edge edge = new Edge();
    				edge.a = scan.nextInt();
    				edge.b = scan.nextInt();
    				edge.weight = scan.nextInt();
    				k.edges.add(edge);
    				//add里edge传入的是地址, 不new的话所有的edges将指向同一个edge, 里面的数据会全都一样
    			}
    			k.init(n);
    			Collections.sort(k.edges, Edge.edgeCmp);
    			
    			int ans = 0;
    			for(int i=0; i<m; i++) {
    				int fa = k.find(k.edges.get(i).a);
    				int fb = k.find(k.edges.get(i).b);
    				if(fa!=fb) {
    					//如果两端点不在同一颗树,则合并两节点
    					k.parent[fa] = fb;
    					ans+= k.edges.get(i).weight;
    				}
    			}
    			System.out.println(ans);
    		}
    		
    	}
    	static class Edge{
    		int a, b, weight;
    		public static Comparator<Edge> edgeCmp = new Comparator<Edge>() {
    			//升序排序
    			public int compare(Edge e1, Edge e2) {
    				if(e1.weight > e2.weight)
    					return 1;
    				else if(e1.weight<e2.weight)
    					return -1;
    				else return 0;
    			}
    		};
    	}
    	static class Kruskal{
    		ArrayList<Edge> edges= new ArrayList<Edge>();
    		int parent[];
    		int find(int x) {
    			//找最终的root
    			return x == parent[x]?x:(find(parent[x]));
    		}
    		void init(int n) {
    			for(int i=1; i<=n; i++)
    				parent[i] = i;
    		}
    	}
    }
    ```

0.0分

0 人评分

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

斯巴达

TA的其他文章

你可能喜欢

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

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

C语言训练-计算1977！* （C语言代码）

C二级辅导-分段函数（C语言代码）

输出九九乘法表（C语言代码）

1729: 还是畅通工程(Kruskal) java写法

评论区

精彩推荐

汽水瓶（C语言代码）

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

九宫重排（C++代码）

【数组的距离】（C语言代码）

不容易系列2 （C语言代码）

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

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

WU-图形输出（C++代码）

C语言考试练习题_保留字母（C语言代码）

时间转换（C语言代码）

斯巴达

TA的其他文章

你可能喜欢

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

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

C语言训练-计算1977！* （C语言代码）

C二级辅导-分段函数 （C语言代码）

输出九九乘法表 （C语言代码）

1729: 还是畅通工程(Kruskal) java写法

评论区

精彩推荐

汽水瓶 （C语言代码）

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

九宫重排 （C++代码）

【数组的距离】 （C语言代码）

不容易系列2 （C语言代码）

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

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

WU-图形输出 （C++代码）

C语言考试练习题_保留字母 （C语言代码）

时间转换 （C语言代码）

C二级辅导-分段函数（C语言代码）

输出九九乘法表（C语言代码）

　　评论区

汽水瓶（C语言代码）

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

九宫重排（C++代码）

【数组的距离】（C语言代码）

WU-图形输出（C++代码）

C语言考试练习题_保留字母（C语言代码）

时间转换（C语言代码）