李华

用户名：2645479600

访问量：17680

签　名：

等　　级
排　　名	469
经　　验	4571
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）
浏览：1064

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs
浏览：889

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1406

你可能喜欢

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细

　　作者: 李华　　　　发表时间：2020-02-20 15:24:57 浏览：1406　|　评论：4　

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

#### **注意:全篇我主要用C语言来写,但是调用了STL里面的排序,提交的时候要提交C++。排序部分也可以用C语言实现，只是麻烦了一点,排序要注意时间复杂度,否则10000个岛可能会超时,尽量用“快排”。**
**需要学过的知识:并查集,dfs,最小生成树。建议学过这些再来做这道题啦，暴力很容易超时或者超空间。B站有很多这类视频，找不到可以私信......**

解题思想:
题目告诉我们各个桥的天数,如果桥前一天还在,第二天没了,那么就会抗议一次------------------------注意读懂这句话。我们举样例为例子,第一天后2,3之间的桥断了。但是2和3之间还是可以走通的,不会抗议。第二天后1,2和1,3两座桥断了,居民会抗议,两个桥断了,都影响到了岛之间的通行,但是只记录一天(所以代码里面对这个情况要特殊处理)。第三天后3,4之间断了，导致3,4,之间不能走通,会抗议。所以总共抗议两天

逆向思维:从第一到第三天,前一天有桥,第二天桥毁了的抗议天数是2。我们可以想象一下场景,把时空倒转。逆着来,从第三天到第一天,第三天后的时候没有桥,第三天时我们恢复了一座桥,并且可以影响到岛与岛之间的连接,抗议天数+1。第二天后,此时仅有一座桥连通(3,4),第二天时,我们恢复了两座桥(1,2)(1,3)，影响到了岛与岛之间的连接，抗议天数+1。后面的代码我们会把这样影响到了连接的桥称为"有效桥"。第一天后,我们有三座桥了。第一天时,恢复了（2,3）这座桥，但是有没有这座桥。2和3之间都能连通,所以抗议天数不会加。总共抗议两天。
那么我们就将毁桥的过程转换为了恢复桥的过程,即建桥。那么就可以把这道题看成建最小生成树的题目,如果建立了n-1条有效桥,那么各个岛就连接成功了,剩下的桥不需要判断。用并查集的思想,我们将桥按天数大小，从大到小排序，我们依次枚举每座桥,每建成一座桥,我们就检查该桥的两个岛是否同根,如果同根,代表这是条无效桥,不用理它。如果两个岛不同根代表将会产生新的连接,这是有效桥,然后我们将(x,y)中的y及与y连接的岛全部归到x中。每产生一次有效桥我们就判断是否与上一次产生的有效桥天数相同,相同的话，抗议天数不能叠加,不同的话就让抗议天数加一。

比较啰嗦比较长，如果有错误的地方，麻烦大家指出。

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int n,m;	//n个岛,m座桥 
    int ans;	//抗议天数 
    int num;	//有效桥个数 
    struct land
    {
    	int x;	//起点 
    	int y;	//终点 
    	int t;	//桥的天数 
    };
    land island[100005];	//最多有十万座桥 
    int f[10005];	//并查集的数组
    int last_time;
    void Init ()
    {
    	for(int i=0;i<n;i++)
    	{
    		f[i]=i;
    	}
    } 
    bool cmp(land x,land y)
    {
    	return x.t>y.t;
    }
    int getf(int x)
    {
     	if(x==f[x])	//如果并查集下标等于内部值,代表它就是根
    	{
    		return x;
    	} 
    	 else
    	{
    	 	f[x]=getf(f[x]);	//沿途遍历的元素全部归到根,即为路径压缩 
    	 	return f[x];
    	}
    }
    int merge(int v,int u)
    {
    	//判断是否同根,同根则代表已连通,不同根代表未连通,这是有效桥
    	int t1,t2;
    	t1=getf(v);	//getf函数用来找寻其根 
    	t2=getf(u);
    	if(t1!=t2)	//如果不同根
    	{
    		f[t2]=t1;	//t2及t2后代全部归到t1
    		return 1; 
    	} 
    	return 0;	//同根则返回假 
    }
    int main()
    {
    	//1.输入全部的桥
    	//2.初始化并查集
    	//3.将桥按桥的时间从大到小排序
    	//4.将m行指令枚举
    	//5.如果输入的桥的根和要连接的桥不属于同一个根,代表不属于同一个集合
    	//  那么说明有新的"可以让原集合连接到外处"的桥出现了(同一个集合内的岛可以相互达到,看作为一体的),我们称之为有效桥 
    	//6. 如果有"有效桥"出现了,那么我们记录这个桥的时间,如果该"有效桥"的时间和前一座"有效桥"的时间不同,那么投诉天数加一
    	//7.如果时间相同,代表同一天出现两座桥，但是居民只会抱怨一天
    	//8.**核心**:逆向思维,按照天数递减的顺序建树,如果之前没有这座桥,突然有这座桥了,那么就会抱怨 
    	scanf("%d %d",&n,&m);
    	for(int i=0;i<m;i++)
    	{
    		scanf("%d %d %d",&island[i].x,&island[i].y,&island[i].t);
    	}
    	Init();	//将并查集初始化
    	sort(island,island+m,cmp);
    	for(int i=0;i<m;i++)	//枚举m座桥 
    	{
    		if(merge(island[i].x,island[i].y))	//如果这两个点没有被连通,那么就是有效桥 
    		{
    			//出现有效桥了,就对比一下是否与上一次的有效桥时间相等。
    			if(island[i].t!=last_time)
    			{
    				ans++;
    				last_time=island[i].t;//记录下它的时间,同时间的桥只能抗议一次
    			}
    			num++;	//num代表有效桥的数量
    		}
    		if(num==n-1)	//如果达成最少边的生成树,既全部岛已连通就不用再判断了
    		{
    			break;
    		} 
    	}
    	printf("%d",ans);
    	return 0;
    }

0.0分

20 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

flags

很清晰的思路

2020-11-29 14:26:45

一起闹〆朱瑞晗

第19行是不是小于等于n啊

2020-04-27 17:30:59

uq_41087421161

大佬

2020-02-20 19:06:39

Two.

有点儿牛逼

2020-02-20 19:04:51

李华

TA的其他文章

你可能喜欢

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

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

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

C二级辅导-阶乘数列（C语言代码）

C二级辅导-进制转换（C语言代码）

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细

评论区

精彩推荐

校门外的树（C++代码）

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

【回文数(二)】（C++代码）

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

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

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

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

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

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

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

李华

TA的其他文章

你可能喜欢

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

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

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

C二级辅导-阶乘数列 （C语言代码）

C二级辅导-进制转换 （C语言代码）

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细

评论区

精彩推荐

校门外的树 （C++代码）

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

【回文数(二)】 （C++代码）

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

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

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

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

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

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

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

C二级辅导-阶乘数列（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

校门外的树（C++代码）

【回文数(二)】（C++代码）