【蓝桥杯】 历届试题 国王的烦恼(并查集)

2024-03-30 13:08

本文主要是介绍【蓝桥杯】 历届试题 国王的烦恼(并查集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

历届试题 国王的烦恼

问题描述

C 国由 n n n 个小岛组成,为了方便小岛之间联络,C 国在小岛间建立了 m m m 座大桥,每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而,由于海水冲刷,有一些大桥面临着不能使用的危险。

如果两个小岛间的所有大桥都不能使用,则这两座小岛就不能直接到达了。然而,只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达,他们就会安然无事。但是,如果前一天两个小岛之间还有方法可以到达,后一天却不能到达了,居民们就会一起抗议。

现在 C 国的国王已经知道了每座桥能使用的天数,超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。

输入格式

输入的第一行包含两个整数 n , m n, m n,m,分别表示小岛的个数和桥的数量。
接下来 m m m 行,每行三个整数 a , b , t a, b, t a,b,t,分别表示该座桥连接 a a a 号和 b b b 号两个小岛,能使用t天。小岛的编号从 1 开始递增。

输出格式

输出一个整数,表示居民们会抗议的天数。

样例输入

4 4
1 2 2
1 3 2
2 3 1
3 4 3

样例输出
2
样例说明

第一天后 2 和 3 之间的桥不能使用,不影响。
第二天后 1 和 2 之间,以及1和3之间的桥不能使用,居民们会抗议。
第三天后 3 和 4 之间的桥不能使用,居民们会抗议。

数据规模和约定

对于 30% 的数据, 1 ≤ n ≤ 20 , 1 ≤ m ≤ 100 1\leq n \leq 20,1 \leq m \leq 100 1n201m100
对于 50% 的数据, 1 ≤ n ≤ 500 , 1 ≤ m ≤ 10000 1 \leq n \leq 500,1 \leq m \leq 10000 1n5001m10000
对于 100% 的数据, 1 ≤ n ≤ 10000 , 1 ≤ m ≤ 100000 , 1 ≤ a , b ≤ n , 1 ≤ t ≤ 100000 1 \leq n \leq 10000,1 \leq m \leq 100000,1\leq a, b \leq n, 1 \leq t \leq 100000 1n100001m1000001a,bn1t100000



—— 分割线之初入江湖 ——


分析:
这道题一定要认真读题
题中有句话:“如果前一天两个小岛之间还有方法可以到达,后一天却不能到达了,居民们就会一起抗议”。这句话针对的仅仅是某两座小岛,而并非所有的小岛,举个例子,如下图所示:
第1天
第1天,所有小岛均正常,无任何居民抗议
第2天,桥d损坏(如下图所示),此时小岛3和小岛4的居民由于在第1天能互通而现在不能互通,于是开始抗议。这是抗议的第1次。
第2天
第3天,桥c损坏(如下图所示),此时小岛1和小岛3仍能互通(通过小岛2),因此无任何居民抗议。此时你肯定有疑惑了,为什么小岛3和小岛4的居民不抗议呢?如果你产生了这样的疑惑,那么恭喜你,你和我犯了一样的错!兄弟,看清题目:“如果前一天两个小岛之间还有方法可以到达,后一天却不能到达了,居民们就会一起抗议”。在第2天的时候,小岛3和小岛4就已经不互通了,现在到了第3天它们依然不互通,所以根本不会抗议!
第3天
因此我们得出结论:抗议与否是由两个小岛在两天之间是否发生了连通分支数增加的事件所决定的,换言之,一旦某个桥的损坏导致了两个小岛不互通,就仅仅是会抗议那一天,之后就没它们的什么事儿了。
都走到这步了,我们就继续演示这个过程吧
第4天,桥a损坏(如下图所示),此时小岛1和小岛3的居民由于在第3天能互通而现在不能互通,于是开始抗议。这是抗议的第2次。
第4天
第5天,此时桥b仍未损坏(如上图所示),由于在第4天的时候小岛1与小岛2、小岛1与小岛3、小岛3与小岛4均不能互通,而在第5天的情况依然如此,所以此时没有任何居民会抗议
第6天,桥b损坏(如下图所示),显然此时小岛2与小岛3的居民会抗议,这是抗议的第3次
第5天

于是对于我给出的这个测试样例,程序最终应该输出 3。

上述演示过程实际上也给我们提供了一种解题的思路:模拟
怎么个模拟法?很简单,首先我们定义一个结构体Bridge(包含了桥的可用天数day,以及其连接的两座小岛的序号x和y),如下:

struct Bridge		//代表桥 
{int x,y;		//表示桥连接的两个地方 int day;		//表示这个桥的可用时限(天数)Bridge(){ }Bridge(int a,int b,int c):x(a),y(b),day(c){ } 
};

然后把输入的多个桥的数据放进一个Bridge型数组中,并根据这些桥的可用时限进行一个升序排序
在录入桥的信息后,我们通过并查集来将把这些桥的联通情况记录下来
接着,就开始模拟上面的过程了
首先是一个循环i,该循环的次数为录入的桥的数量,循环里的内容如下:
模拟当前的桥bridge[i]损坏,并判断此时整个小岛所构成的并查集中是否有发生连通分支数的增加
如果是:说明桥bridge[i]的损坏会导致其连接的两个小岛的居民抗议,于是执行ans++
否则:说明桥bridge[i]的损坏不会使其连接的两个小岛的居民抗议,因此不执行ans++
最后输出答案即可
不过有一个情况似乎被遗漏掉了,接下来我们看一下另一组测试数据(情况如下):
特殊情况
注意到可用时限为1天的桥有两座(桥b和桥c),那么在第2天时,小岛1和小岛3、小岛3和小岛4的居民就由第1天的能互通变成了现在的不互通,因此ans++。但是我们的程序是顺序执行的(通过一个循环),因此在执行的时候会将这种情况作为两次不同的情况来处理,于是会导致程序ans++两次。而实际上,尽管那一天是两座桥损坏,但是却是再同一天啊!因此居民只会抗议那一天!
处理这个情况很简单,我们只需要在i循环内,预先探测下一个桥的可用时限(bridge[i+1].day)。这样在循环时,我们每次都先用bridge[i+1].day来和当前桥的使用时限(bridge[i].day)进行对比,如果两个天数不一致,则直接模拟当前桥被损坏的过程;否则,跳过当前循环。这样一来就能避免在这种情况下执行两次(甚至更多的)ans++。

这样的思路很清晰,也很简单。但是往往想法很美好,现实却很残酷。
对于i循环,其循环次数为桥的数量,题目给的最大的桥的数量为105
而在i循环内部,模拟桥bridge[i]损坏却相当麻烦,因为每当某座桥损坏,我们都必须重新将剩下的所有小岛进行一个Unite操作,然后再扫描所有小岛构成的并查集,以检测其连通分支数是否发生改变。在这个过程中,将剩下的小岛进行Unite操作是一个O(n)级别,扫描小岛构成的并查集也是一个O(n)级别。即,在i循环内部是一个2*O(n)级别的操作
综上,此种方法下,程序的时间复杂度在O(n2)级别,那么在105的极限情况下,程序必然超时无疑
因此我们必须换一种思路(个人认为,当换了这样的思路之后,整个题的大门就立刻被打开了)



—— 分割线之踏雪寻梅 ——


题目要我们做的是求居民抗议的天数。如果从一开始去模拟一座桥一座桥的坏掉,那有可能遇到很坏的情况——在很后面才遇到那个割线(离散数学术语,表示当当前边被除去后,整个图的连通分支数就由1变为了2)。而你在每一次坏掉一座桥的时候都需要从头去联合这些桥以判断所有小岛的连通性,这样必然会超时。那我们完全可以逆向思维,不去模拟桥的坏掉,而是去模拟“桥的修建”!!!这样一来我们的程序就只需要循环一次去联合(unite)这些桥,一旦出现某座桥在进行Unite操作时,该桥的Unite操作导致了其连接的两个小岛的代表元发生变化(说明该桥是一条割线),就表示这个桥的损坏会使某两个小岛的居民由前一天的互通变为后一天的不互通,也就是说需要执行一次ans++。采用这样逆向修建的思路,我们就需要将给出的测试数据由桥的使用时限进行降序排序(此时使用时间最长的就是最开始被枚举的!因为它最晚坏,所以在逆向看来它是最先修建的)。
接下来我们用题目给的测试数据进行一个演示(已经进行了降序排序):
测试数据
首先一开始(第4天),是4座互相孤立的小岛,此时所有居民均不互通,如下:
第4天
① 时间来到第3天,小岛3和小岛4之间的桥被修建好(如下图所示),那么此时小岛3和小岛4的居民就由第4天的不互通变成了现在的互通。反过来就是在第3天时小岛3和小岛4的居民互通,但是在第4天就不互通了,因此这两座小岛上的居民会抗议,即ans++。
第3天
② 接下来是第2天,修建了小岛1和小岛2之间的桥(如下图所示)
第2天
此时小岛1和小岛2的居民由第3天的不互通变成了现在的互通。反过来就是在第2天时小岛1和小岛2的居民互通,但是在第3天就不互通了,因此这两座小岛上的居民会抗议,即ans++。
现在有个问题,在天数为2的小桥中,还有一座啊!接下来程序继续扫描,遇到了同样是使用时限为2的另一座小桥,但是它连接的是小岛1与小岛3(此时情况如下)。
第2天
根据上面的分析:小岛1和小岛3的居民由第3天的不互通变成了现在的互通。反过来就是在第2天时小岛1和小岛3的居民互通,但是在第3天就不互通了,因此这两座小岛上的居民会抗议,即ans++。
但是实际上,这一天依然还是第2天,也就是说实际情况是:第2天,桥a和桥b都在,小岛1和小岛2、小岛1和小岛3都是联通的,但是在第3天的时候,这两座桥都损坏了,于是小岛1、2、3彼此被分割开,因此这3座小岛的居民就开始抗议,但是仅抗议这1天,即ans++只执行一次。
由于我们的程序是顺序执行的,因此其会将这个情况视为两天不同的情况。我们如何规避?
通过一个lastDay变量即可,这个变量的作用是记录前一次某个桥的使用天数,如果在循环中,检测到当前桥的使用天数和lastDay不相等,并且将当前桥连接的两个小岛进行Unite操作后其确实使得这两个岛的代表元发生了改变,就说明此时需要执行ans++,否则一律不执行。

③ 接下来时间来到第1天,此时所有小岛的连通情况如下图所示:
第1天
这一天,所有小岛之间是保持着连通性的,和第2天情况一样,所以这里不执行ans++。
此时i循环结束,输出ans=2
以上便是通过转换思路后得到的解题方法,可见其时间复杂度仅为O(n),这在m=105的极限情况下仍能保持较好的性能,因此完全可行。



—— 分割线之巫山见云 ——


下面直接给出本题的完整代码:

#include<iostream>
#include<algorithm>
using namespace std;const int N=10010;
const int M=100010;
struct Bridge		//代表桥 
{int x,y;		//表示桥连接的两个地方 int day;		//表示这个桥的可用时限(天数)Bridge(){ }Bridge(int a,int b,int c):x(a),y(b),day(c){ } 
}; 
Bridge bridge[M];	//用于存储所有的桥 
int pre[N];		   	//用于存储每个小岛的“上级” void init(int n)
{for(int i=1;i<=n;i++)pre[i]=i;
}
int find_pre(int n)
{if(pre[n]==n) return n;else return pre[n]=find_pre(pre[n]);
}
bool unite(int x,int y)
{int rootx=find_pre(x);int rooty=find_pre(y);if(rootx!=rooty){pre[rootx]=rooty;return true;}else return false;
}
bool cmp(Bridge a,Bridge b)
{ return a.day>b.day; }int main()
{int n,m,a,b,t;cin>>n>>m;init(n);for(int i=1;i<=m;i++){cin>>a>>b>>t;bridge[i]=Bridge(a,b,t);}sort(bridge+1,bridge+1+m,cmp);int ans=0,lastDay=0;							//lastDay用于探测一次某个桥的生命时限 for(int i=1;i<=m;i++){bool flag=unite(bridge[i].x,bridge[i].y);	//如果为真表示当前这两个岛未联通if(flag && bridge[i].day!=lastDay)	 		//未连通,且此桥的天数是第一次出现,那么就增加了抗议的天数 {ans++;lastDay=bridge[i].day;}}cout<<ans<<endl;return 0;
}

END


这篇关于【蓝桥杯】 历届试题 国王的烦恼(并查集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/861565

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

poj 1182 并查集 食物链类

题意: 有n只动物,分别编号1....n。所有动物都属于A,B,C中的一种,已知A吃B,B吃C,C吃A。 按顺序给出下面两种共K条信息: 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错,有可能有的信息和之前给出的信息矛盾,也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析: 对于每只动物,创建3个元素 i

POJ1988带权并查集

M u v 将u所在的堆移动到v所在的堆的上面 C u 求u的下面有多少块 带权并查集 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;i

POJ1703带权并查集

D: u v  u与v在不同的集合 A: u v  查询u与v的关系 1)压缩路径过程        fu->root   0  1  u-fu 0                 0  1   1                 1  0 2)合并过程 fu->fv      u->fu   0 1   v->fv 0            1 0 1            0

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

并查集基础与简单扩展应用

并查集 基础题目路径压缩 扩展应用扩展题目1扩展题目2 并查集的结构是一棵树 并查集有两种功能,一种是判断两个元素是否在同一集合,第二种是合并两个集合 并查集的实现需要记录每个节点的父亲节点 判断两个元素是否在同一集合,即判断两个元素的祖宗节点是否是一个节点(祖宗代表整棵树的根节点) 合并两个集合,即将任意一个集合祖宗的爸爸改为另一个集合的祖宗 基础题目 一共有

nyoj99(并查集+欧拉路+dfs)

单词拼接 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 5 描述 给你一些单词,请你判断能否把它们首尾串起来串成一串。 前一个单词的结尾应该与下一个单词的道字母相同。 如 aloha dog arachnid gopher tiger rat   可以拼接成:aloha.arachnid.dog.gopher.rat.tiger 输入 第一行是一个整

nyoj42(并查集解决欧拉回路)

一笔画问题 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 4 描述 zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。 规定,所有的边都只能画一次,不能重复画。   输入 第一行只有一个正整数N(N<=10)表示测试数据的组数。 每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<

【HDU】5222 Exploration(并查集+拓扑排序)

对于无向边使用并查集合并成一个集合,对于有向边使用判断是否存在环 唯一无语的地方就是看输入是百万级的,加个输入挂跑9s,不加挂跑了5s #include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;#pragma comment(linker, "/STACK:102