蓝桥杯历届试题-国王的烦恼（C++代码）并查集&生成树

903 阅读 6 评论 0 点赞

```cpp
注意：同一天内有一个或多个城市没有与外界连接的桥了，那么抗议天数也只是一天 
重点：会并查集，生成树；
难点：读懂题！！！读懂题！！！读懂题！！！（一个城市蹦了只会抗议一天，或者说一次，之后就不抗议了，阅读理解杯！！！）

#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"

using namespace std;

typedef long long ll;
const int maxn = 10010;

typedef struct {
	int x, y;	//存边
	int day;	 //存值
}Edge;

int n, m, fa[maxn];	//fa : 并查集核心数组
vector<Edge> E;		//存边、权

/** 按照边权从大到小排序 */
bool cmp(Edge a, Edge b) {
	return a.day > b.day;
}

/** 初始化并查集数组 */
void init() {
	for(int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
}

/** 找祖宗 */
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

/** 生成树kruskal算法核心(并查集 + 排序) */
int kruskal() {
	init();	//初始化
	sort(E.begin(), E.end(), cmp);	//排序
	int res = 0, Time = -1;	
	//res : 结果，从边权最大的点开始，直到最后整颗树生成一共有多少城市GG
	//Time : 用于防止同一天多个城市的居民一起抗议而造成错加
	for(int i = 0; i < m; ++i) {
		int p1 = find(E[i].x);
		int p2 = find(E[i].y);
		if(p1 != p2) {
			fa[p2] = p1;
			//判断现在这个桥是否断的时间与上一个桥相同
			if(E[i].day != Time) {
				res++;		//又一个城市陷入水生火热之中 (逃
				Time = E[i].day;	//更新时间
			}
			n--;	//生成树核心，最小生成树只能有n - 1条边
			//你也可以用一个 cnt 从 0 加到n - 1 break
		}
		if(n == 1) {	//该结束了
			break;
		}
	}
	return res;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; ++i) {
		Edge data;
		cin >> data.x >> data.y >> data.day;
		E.push_back(data);
	}
	cout << kruskal() << endl;
	return 0;
}

ps：我经过了3次wa才读懂这个题想要干什么 (逃
```

0.0分

7 人评分

本文分类：题解列表
浏览次数：903 次浏览
发布日期：2019-07-15 01:12:08
本文链接：https://blog.dotcpp.com/a/60737

上一篇 > 数字整除-题解(C语言代码)
下一篇 > [编程入门]数组插入处理-题解(C语言代码)

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

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

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

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

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

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

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

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

评论列表共有 6 条评论

zjh 5年前回复TA

@fenny 一个很简单的例子两个结点A，B，我们只看结点A，有两条无向边，第一条权值是1，第二条权值是3，第一天所有边权值减一，第一条权值为0，根据题意，该边以断，但是A，B两个城市还有另一条边连接，权值是2，也就是说在最大一条边断之前，所有比这条边小的都断了，但该点还不是孤儿点，要等连接A权值最大的那条边断了才算A结点没有与外界其他点相连的桥了，这时候居民才会抗议，也就是说，我们只需要看每个点所有边中最大的那条边就可以知道该点什么时候没有与其他点相连的边

zjh 5年前回复TA

@fenny 假设结点有3条边，权值分别是1,2,5，每天权值-1，第一天权值1的边断了，其他两条边还连着权值分别在1,4..... 当它最大的一条边断了的时候才会形成没有任意一个点可以直接或间接的到达这个点，这个点就成了孤儿点，也就会抗议，所以这里用最大生成树，你可以按照样例画图理解一下

fenny 5年前回复TA

@fenny @speaksoftly 你这个应该叫最大生成树，想了一下，大概明白了是怎么一回事，不过仍有比较疑惑的地方，比如为什么要从权值大的开始，如果有图片就好理解了

zjh 5年前回复TA

@fenny 说错了，唯一需要处理的是同一天，有不同结点的边权值一样的情况需要处理

zjh 5年前回复TA

@fenny 并查集、kruskal模板代码，唯一需要处理的是边权为负的情况

fenny 5年前回复TA

妈耶，看不懂

蓝桥杯历届试题-国王的烦恼 （C++代码）并查集&生成树

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 6 条评论

发表评论 取消回复

蓝桥杯历届试题-国王的烦恼（C++代码）并查集&生成树

评论列表共有 6 条评论

发表评论取消回复