国王的烦恼蓝桥杯

题意

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

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

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

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

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

解题思路

这个当初看错了题目，人家问的是居民抗议的天数而不是第几天开始抗议。

这个思路自己开始想的是使用广搜，很基本的思路，但是不大行，因为每次一个桥断了后，有可能会一个连通集一份为二，这样的话我们就不大后判断了，最后还是看的题解。

这里题解说的思路很清奇，题目是桥断了，让我们去判断会不会出现一个新的连通集，其实我们可以反过来，如果我们新建一个桥的话使得两个连通集合为一个了，这就和一个桥断了一样，并且关键的是建桥得过程我们可以使用并查集来模拟，这很简单（拆桥就不好模拟了）。接下来就是我们需要明确按照什么顺序来建桥呢？这里我们可以按照桥可以使用得时间从大到小进行排序，因为桥断的时候是使用时间短的先断，这里正好也是反过来。还有一点需要注意的是，如果同一天出现多个桥断了，并且导致多个点无法访问了，那么居民的抗议也是一天，关于这个处理可以看代码实现。

代码实现

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<sstream>
typedef long long ll;
using namespace std;
const double esp=1e-6;
const int inf=0x3f3f3f3f;
const int MAXN=1E4+7;
const int MAXM=1E5+7;
struct Edge{
	int be, to, day;
	friend bool operator < (const Edge f, const Edge s){
		return f.day > s.day;
	}
}edge[MAXM];
struct Tree{
	int par, rak;
}tre[MAXN];
int n, m;
void init(){
	for(int i=0; i<n; i++){
		tre[i].par = i;
		tre[i].rak = 0;
	}
}
int find(int x){
	if(x == tre[x].par) return x;
	else return tre[x].par = find(tre[x].par);
}
bool unit(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y)
		return false;
	if(tre[x].rak < tre[y].rak)
		tre[x].par = tre[y].par;
	else {
		tre[y].par = tre[x].par;
		if(tre[x].rak == tre[y].rak)
			tre[x].rak++;
	}
	return true;
}

int main()
{
	int a, b;
	cin>>n>>m;
	init();
	for(int i=0; i<m; i++)
		cin>>edge[i].be>>edge[i].to>>edge[i].day;
	sort(edge, edge+m); 
	int ans=0, pre=0;
	for(int i=0; i<m; i++)
	{
        //pre表示的是上一个桥的建立时间，如果当前的桥建立可以减少一个连通集，但是和上次的建立是相同的话
        //那么就说明同一天可以建立多个桥，并且可以减少多个连通集。
		if(unit(edge[i].be, edge[i].to) && pre!=edge[i].day)
		{
			ans++;
			pre = edge[i].day;
		}
	}
	cout<<ans<<endl;
	return 0;
}