zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-合根植物（C++代码）并查集
浏览：805

蓝桥杯2017年第八届真题-分考场（C++代码）图的染色
浏览：995

蓝桥杯2017年第八届真题-发现环（C++代码）并查集
浏览：1057

你可能喜欢

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

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

　　作者: zjh　　　　发表时间：2019-07-15 01:12:08 浏览：877　|　评论：1　

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

```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分

8 人评分

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

　　评论区

fenny

妈耶，看不懂

2019-07-30 22:36:57

zjh 2019-07-31 12:08:41 |

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

zjh 2019-07-31 12:12:58 |

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

fenny 2019-07-31 20:31:56 |

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

zjh 2019-08-01 02:29:42 |

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

zjh 2019-08-01 02:39:42 |

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

zjh

TA的其他文章

你可能喜欢

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

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

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

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

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

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

整除问题（C语言代码）

Tom数（C语言代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

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

C二级辅导-同因查找（C语言代码）

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

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

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

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

zjh

TA的其他文章

你可能喜欢

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

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

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

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

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

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.1 （C++代码）__gcd()是已经写好的函数，可以直接使用

整除问题 （C语言代码）

Tom数 （C语言代码）

十->二进制转换 （C++代码）（零和负数需要特殊处理）

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

C二级辅导-同因查找 （C语言代码）

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

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

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

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

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

　　评论区

整除问题（C语言代码）

Tom数（C语言代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

C二级辅导-同因查找（C语言代码）