蓝桥杯国王的烦恼

链接:蓝桥杯国王的烦恼

Description

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

  • 如果两个小岛间的所有大桥都不能使用,则这两座小岛就不能直接到达了。然而,只要这两座小岛的居民能通过其他的桥或者其他的小岛

  • 互相到达,他们就会安然无事。但是,如果前一天两个小岛之间还有方法可以到达,后一天却不能到达了,居民们就会一起抗议。

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

    Input

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

    Output

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

    Sample Input

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

    Sample Output

    2

    题解

  • 一道很简单的并查集,拆了就不连通,相当于加上才连通
  • 然后并查集维护一下就ok了,然后要注意的是时间相同的点的处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e7;
int f[N],n,m,ans;
struct node{
int u,v,w;
}e[N];

bool cmp(node x,node y){
return x.w>y.w;
}

void readin(){
ios::sync_with_stdio(false);
cin>>n>>m;
rep(i,1,m)cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1,cmp);
rep(i,1,n)f[i]=i;
}

int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
int un(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
f[x]=y;
return 1;
}
return 0;
}
void solve(){
readin();
int pre=-1;
rep(i,1,m)if(un(e[i].u,e[i].v)&&pre!=e[i].w)ans++,pre=e[i].w;
cout<<ans<<endl;
}

int main(){
solve();
return 0;
}