龚秋志

用户名：uq_48078956563

访问量：48438

签　名：

等　　级
排　　名	34
经　　验	13257
参赛次数	30
文章发表	64
年　　龄	19
在职情况	学生
学　　校	湖北生物科技职业学院
专　　业	计算机应用

　　自我简介：

TA的其他文章

母牛的故事_题解三种解法，递归；记忆型递归；动态规划
浏览：25622

DFS深度优先搜索两种实现方式(递归，栈)
浏览：427

信息学奥赛一本通T1249- Lake Counting (BFS,DFS) java 题解
浏览：169

你可能喜欢

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

蓝桥杯历届试题-国王的烦恼-题解（Java代码）克鲁斯卡尔+并查集+最小生成树(逆序，从大到小)

　　作者: 龚秋志　　　　发表时间：2020-10-08 10:11:31 浏览：1487　|　评论：1　

原题链接：蓝桥杯历届试题-国王的烦恼

## 解题思路： 
  把桥看成边, 小岛看成点,  能使用的天数看成权重
  ![](/image_editor_upload/20201008100306_89264.jpg)
   1.根据使用天数（权重）从大到小排序 
 	2.建立最小生成树(逆序,从大小)   2.建立最小生成树(逆序,从大小) 
 	3.建立的时候首先判断两个点是否是已经连通的
	4.如果是则说明两个这条边不重要，如果不是则说明这条边很重要一旦这条边小时居民就会抗议

**注意**：如果同一天消失**多条边**那么居民也只会抗议**一天**
**注意**：建立树的时候不能形成**回路**，就是说都不能是同一个**根节点**
![](/image_editor_upload/20201008100601_23462.jpg)
####  最小生成树(逆序)
![](/image_editor_upload/20201008101013_70650.jpg)
## 参考代码：
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

/**
 * 
 
 * 
 */
class LDDD {
	public int u;// 起点的小岛
	public int v;// 终点的小岛
	public int w;// 使用的天数 也就是权重

public LDDD(int u, int v, int w) {
		this.u = u;
		this.v = v;
		this.w = w;
	}
}

public class 国王的烦恼 {

// 存储每个点的根节点 下标表示该点 值表示该点的根节点
	// 默认每个点的根节点是当前点
	static int[] f;

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();// 小岛的数量
		int m = sc.nextInt();// 桥的数量

LDDD[] arr = new LDDD[m];// 存储输入的边
		f = new int[n];

for (int i = 0; i < m; i++) {
			arr[i] = new LDDD(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
		}

// 排序 按照使用的天数也就是权重进行从大到小排序
		Arrays.sort(arr, new Comparator<LDDD>() {
			@Override
			public int compare(LDDD o1, LDDD o2) {
				// o1.w > o2.w ? -1 : 1之前这样写没有返回0 然后网站一直报运行错误 看来必须要返回0了
				return o1.w == o2.w ? 0 : (o1.w > o2.w ? -1 : 1);
			}
		});
		// 初始化每个点的根节点 默认是自己
		for (int i = 0; i < n; i++) {
			f[i] = i;
		}

// pre用来判断是不是今天
		// ans用来统计居民抗议的天数
		int pre = -1, ans = 0;

// 遍历每一天 开始逆序生成最小生成树 (其实我觉得可以叫成最大生成树)
		for (int i = 0; i < m; i++) {
			// 判断出发点和终点是否已经连通了
			// 说白了就是判断两个点是否形成了回路
			boolean flag = merge(arr[i].u, arr[i].v);
			// 如果该点没有连通那么就说明这条边是必须要有的,如果没有居民就会抗议
			// 注意： 仔细看题如果同一天消失两条边 那么居民还是只会抗议这一天
			if (!flag && arr[i].w != pre) {
				ans++;// 居民抗议的天数加一
				pre = arr[i].w;
			}
		}
		System.out.println(ans);
	}

// 并查集模板代码
	// 寻找x点的根节点
	public static int Find(int x) {
		if (f[x] == x) {
			return x;
		} else {
			return Find(f[x]);
		}
		// 也可以用三元运算符的写法
		// return f[x]==x?x:Find(f[x]);
	}

// 判断v点和u点在最小生成树里面是不是连通的
	public static boolean merge(int v, int u) {
		v = Find(v);
		u = Find(u);
		// 判断这两个点是否是同一个根节点
		// 也就是说判断是否为回路(这句话不理解也没关系)
		if (v != u) {
			f[u] = v;
			return false;
		}
		return true;
	}

}

```

0.0分

17 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

王玉辰

流弊

2020-10-08 14:30:37

龚秋志

TA的其他文章

你可能喜欢

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

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

C语言训练-斐波纳契数列（C语言代码）

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

P1002 （C语言代码）

蓝桥杯历届试题-国王的烦恼-题解（Java代码）克鲁斯卡尔+并查集+最小生成树(逆序，从大到小)

评论区

精彩推荐

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

【亲和数】（C语言代码）

printf基础练习2 （C语言代码）

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

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

【蟠桃记】（C语言代码）

矩阵加法（C语言代码）

输入输出格式练习（C语言代码）

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

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

龚秋志

TA的其他文章

你可能喜欢

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

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

C语言训练-斐波纳契数列 （C语言代码）

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

P1002 （C语言代码）

蓝桥杯历届试题-国王的烦恼-题解（Java代码）克鲁斯卡尔+并查集+最小生成树(逆序，从大到小)

评论区

精彩推荐

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

【亲和数】 （C语言代码）

printf基础练习2 （C语言代码）

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

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

【蟠桃记】 （C语言代码）

矩阵加法 （C语言代码）

输入输出格式练习 （C语言代码）

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

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

C语言训练-斐波纳契数列（C语言代码）

　　评论区

【亲和数】（C语言代码）

【蟠桃记】（C语言代码）

矩阵加法（C语言代码）

输入输出格式练习（C语言代码）