JHwong

用户名：dotcpp0724243

访问量：833

签　名：

等　　级
排　　名	3383
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

1435: 蓝桥杯历届试题-国王的烦恼
浏览：156

1427: 蓝桥杯2013年第四届真题-买不到的数目
浏览：39

2529: NOIP2012-同余方程-了解即可
浏览：34

你可能喜欢

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

1435: 蓝桥杯历届试题-国王的烦恼

　　作者: JHwong　　　　发表时间：2024-02-06 19:18:58 浏览：156　|　评论：1　

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

# 1435: 蓝桥杯历届试题-国王的烦恼
## 抽象题意
按照题目含义，在某一天内只要发生两个小岛是不可相互抵达的就会发生抗议。还需要注意在同一天发生的抗议仅计算一次。考虑到我们要求解的是抗议次数。不妨先记抗议次数为 answer 。综上描述，触发 answer += 1 的条件是**某一天内存在两个小岛不可相互抵达**。
接下来，继续抽象条件。注意到题目是的逻辑数据结构一定是图，因此考虑抽象为图论问题，或者基于图论可以解决。至此转义语义，能后相互抵达等价于图论中能否连通，桥等价于图论中的边。换言之，目前构成的图我们可以暂且称之为连通图。暂且的理由稍后再说。
如果采用检测的方式来检测连通图是否被破环是不好的，无法通过所有数据。所以要考虑如何转义条件。现在考虑连通图的破坏会带来的后果，最好是数值上的呈现。很快会发现，如果因为某一条桥的破环发生了连通图的结构被破环 --> 数值上，连通图的数量一定会增加,其次这条桥 (边) 就是当前图下的割。于是现在我们有两个角度：**1、求连通图的块数变化；2、求割然后比对**。
分析之后，会发现求割的方式还是不行。因为图的数量有 t 决定，而求解割需要线性的时间。这样子的代价依旧昂贵。**换言之，从题意思路的正面 -- 破环桥 (边) 的思路代价都是巨大的**。
那么考虑反面恢复边的情况，记录连通块的变化。注意因为是反面，所以此时连通图数量会减少而不是增加。此时，我们仍然需要考虑一条边能够连接两个连通图使得连通图个数减少。而能够帮助我们快速实现是否两个点连通的数据结构有并查集。因此考虑并查集来帮助我们实现这个判断的过程。并查集的速度很快 (可以说是接触的大部分数据结构以外最快的，一般认为是$$\alpha(n)$$)，不需要担心判别的超时。至此我们分析出了解题的可能性。

## 代码实现
首先定义出我们的数据结构 -- 边集数组，为了可读性在这道题我们将 bridge[] 替代 edge[]。抽象层面任然是 Edge。设计一点复制用的函数。
```cpp
#define MAX_M 100005
struct Edge {
  int from, to, time;

/* funtion member -- this code for c plus plus 
     if you are coding by c, please write this code 
	 which following independently
  */
  Edge() {}; // default construct function
  Edge(int from, int to, int time) : from(from), to(to), time(time){};

inline void modify(const int data_from, const int data_to, const int data_time) {
	from = data_from;
	to = data_to;
	time = data_time;
  };

/*  there is a trick for sort function */
  bool operator< (const Edge& other) const {
	return time > other.time;
  };
}bridge[MAX_M];
```
按照模板设计一下并查集即可，完整代码如下。这里面设计了加速版的代码 -- 目的是躲避多余的检查。
```cpp
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include <iomanip>
#include <unordered_map>
#include <time.h>

#define MAX_N 10005
#define MAX_M 100005
#define MAX_T 100005
struct Edge {
  int from, to, time;

inline void modify(const int data_from, const int data_to, const int data_time) {
	from = data_from;
	to = data_to;
	time = data_time;
  };

/*  there is a trick for sort function */
  bool operator< (const Edge& other) const {
	return time > other.time;
  };
}bridge[MAX_M];

/*  for quick_set  */
int quick_set[MAX_N], rank[MAX_N];

inline void initilization(int n) {
  for (int i = 1; i <= n; ++i) 
	quick_set[i] = i;
}

int findRoot(int x) {
  while (x != quick_set[x]) {
	quick_set[x] = quick_set[quick_set[x]];
	x = quick_set[x];
  }
  return x;
}

#define quicklyCheckInSameSet(root_x, root_y) ( (root_x) == (root_y) ? true : false )
inline void quicklyUnionSet(int root_x, int root_y) {
  if (bool flag = quicklyCheckInSameSet(root_x, root_y)) return;

if (rank[root_x] < rank[root_y])
	quick_set[root_x] = root_y;
  else
	quick_set[root_y] = root_x;

if (rank[root_x] == rank[root_y])
	++rank[root_x];
}

inline void uninSet(int x, int y) {
  int root_x = findRoot(x), root_y = findRoot(y);
  quicklyUnionSet(root_x, root_y);
}

bool inSameSet(int x, int y) {
  int root_x = findRoot(x), root_y = findRoot(y);
  if (root_x == root_y) return true;
  return false;
}

int n, m;
int main() {
  scanf("%d%d", &n, &m);
  /*  input the edge  */
  {
    int a, b, t; // avoid repeat allocate local value.
    for (int i = 0; i < m; ++i) {
      scanf("%d%d%d", &a, &b, &t);
	  bridge[i].modify(a, b, t); // bridge[i] = { a, b, t };
	}
  }

initilization(n);
  std::sort(bridge, bridge + m);
#define MAX_INT 0x3f3f3f3f
  int ans = 0, last_day = MAX_INT;
  bool if_not_in_same_set = 0;
  for (int i = 0; i < m; ++i) {
	int from = bridge[i].from, to = bridge[i].to, time = bridge[i].time;
	from = findRoot(from), to = findRoot(to);
	if_not_in_same_set = !quicklyCheckInSameSet(from, to);
	if (if_not_in_same_set && last_day > time) {
	  ++ans;
	  last_day = time;
	}
    quicklyUnionSet(from, to);
  }
    
	/*  output the answer  */
  printf("%d\n", ans);
  return 0;
}
```
并不清楚还能不能优化。

0.0分

2 人评分

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

　　评论区

JHwong

还是存在一点内存引用的冗余的，可以替换成局部变量。但是估计就快几毫秒，提升意义不是很大。总体上来讲，性能提升很多了。同算法其他部分实现的2倍。

2024-02-06 21:44:53

JHwong

TA的其他文章

你可能喜欢

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

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

C二级辅导-等差数列（C++代码）

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

C二级辅导-统计字符（C语言代码）

1435: 蓝桥杯历届试题-国王的烦恼

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

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

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

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

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

淘淘的名单（C语言代码）

WU-小九九（C++代码）

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

JHwong

TA的其他文章

你可能喜欢

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

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

C二级辅导-等差数列 （C++代码）

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

C二级辅导-统计字符 （C语言代码）

1435: 蓝桥杯历届试题-国王的烦恼

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

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

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

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

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

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

淘淘的名单 （C语言代码）

WU-小九九 （C++代码）

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

C二级辅导-等差数列（C++代码）

C二级辅导-统计字符（C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

淘淘的名单（C语言代码）

WU-小九九（C++代码）