1eHz

用户名：dxy1397

访问量：16252

签　名：

等　　级
排　　名	1118
经　　验	3195
参赛次数	0
文章发表	15
年　　龄	0
在职情况	学生
学　　校	武汉
专　　业

　　自我简介：

TA的其他文章

✔✔✔ 树的直径问题+DFS求解 [c++]
浏览：913

你可能喜欢

A+B for Input-Output Practice (III) （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

蓝桥杯历届试题-国王的烦恼-题解（C++代码）kruskal算法最小生成树逆向

　　作者: 1eHz　　　　发表时间：2020-08-24 19:39:59 浏览：789　|　评论：2　

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

这题的关键是最小生成树算法，这里用的是**kruskal算法**。
注：**每有小岛变为不连通时居民抱怨一次，一天抱怨多次只计抱怨一天**。
可以逆向思考这道题，从反向出发将题目条件转化为：每有小岛变为连通时居民抱怨一次。
将小岛视为点，桥视为边，桥的有效时间视为边的权，将其整体视作一个无向图。
再在这个无向图里**逆向**（权值从大到小）建立最小生成树，最后问题是求这个**最小生成树权值不同的边的个数**。

```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, fa[10001];
struct edge{
	int head, tail, power;
}eg[100001];
bool edgeCmp(edge a, edge b){
	return a.power > b.power;
}

int findFa(int x){
	return fa[x]==x?x:fa[x]=findFa(fa[x]);
}
void merge(int a, int b){
	fa[findFa(a)] = findFa(b);
}

int kruskal(){
	int res = 0, cnt = 0, day = 0;
	//res:权值不同的边的个数、cnt:生成树当前的边数、day:第几天（或边的权）
	for(int i=1;i<m;i++){
		if(findFa(eg[i].head) == findFa(eg[i].tail)) continue;
		merge(eg[i].head, eg[i].tail);
		if(day != eg[i].power){
			day = eg[i].power;
			res++;
		}
		cnt++;
		if(cnt+1 == n) break;  //最小生成树已完全生成。
	}
	return res;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>eg[i].head>>eg[i].tail>>eg[i].power;
	sort(eg+1, eg+m+1, edgeCmp);
	for(int i=1;i<=n;i++) fa[i] = i;

cout<<kruskal();
	return 0;
}
```

0.0分

5 人评分

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

　　评论区

Freedom

非常好的思路

2022-07-22 14:19:26

ebork

就是建立最大权重生成树对吧？

2022-06-25 20:20:23

1eHz

TA的其他文章

你可能喜欢

C语言训练-求素数问题（C语言代码）

C语言训练-立方和不等式（C语言代码）

A+B for Input-Output Practice (III) （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

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

蓝桥杯历届试题-国王的烦恼-题解（C++代码）kruskal算法最小生成树逆向

评论区

精彩推荐

C二级辅导-求偶数和（C语言代码）

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

C语言训练-素数问题（C语言代码）

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

1014题解

A+B for Input-Output Practice (IV) （C语言代码）

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

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

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

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

1eHz

TA的其他文章

你可能喜欢

C语言训练-求素数问题 （C语言代码）

C语言训练-立方和不等式 （C语言代码）

A+B for Input-Output Practice (III) （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

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

蓝桥杯历届试题-国王的烦恼-题解（C++代码）kruskal算法最小生成树 逆向

评论区

精彩推荐

C二级辅导-求偶数和 （C语言代码）

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

C语言训练-素数问题 （C语言代码）

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

1014题解

A+B for Input-Output Practice (IV) （C语言代码）

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

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

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

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

C语言训练-求素数问题（C语言代码）

C语言训练-立方和不等式（C语言代码）

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

蓝桥杯历届试题-国王的烦恼-题解（C++代码）kruskal算法最小生成树逆向

　　评论区

C二级辅导-求偶数和（C语言代码）

C语言训练-素数问题（C语言代码）