蓝桥杯 国王的烦恼 (并查集)

问题描述

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

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

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

 

输入格式

输入的第一行包含两个整数n, m,分别表示小岛的个数和桥的数量。

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

 

输出格式

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

 

样例输入

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

 

样例输出

2

 

思路

考虑用并查集来维护所有岛屿之间的连通性,我们可以对所有的边按照使用期从大到小排序(反向思考),然后遍历枚举。

在枚举的过程中,若一条边的两端不在同一个连通块,则说明新增的这一个桥梁会引起群众的抗议,此时 ans++

注意同一天的多次群众抗议我们只统计一次。

 

AC 代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <set>
#include <map>
#include <stack>
#define inf 0x7f7f7f
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
using namespace std;
const int maxn = 1e6 + 10;
typedef long long LL;
int n,m;

struct node{
    int to;
    int from;
    int cost;
    int next;
    friend bool operator<(const node &x,const node &y){
        return x.cost > y.cost;
    }
}edge[maxn];
int head[maxn],tot;
int fa[maxn],rk[maxn];

void init(){
    memset(head,-1,sizeof(head));
    tot = 0;
}

void addedge(int u,int v,int cost){
    edge[tot].to = v;
    edge[tot].from = u;
    edge[tot].cost = cost;
    edge[tot].next = head[u];
    head[u] = tot ++;
}

int find_set(int x){
    if(x != fa[x])
        fa[x] = find_set(fa[x]);
    return fa[x];
}

bool union_set(int x,int y){
    x = find_set(x);
    y = find_set(y);
    if(x==y)return false;
    if(rk[x]>rk[y])
        fa[y] = x;
    else{
        fa[x] = y;
        if(rk[x]==rk[y])
            ++rk[y];
    }
    return true;
}

void solve(){
    memset(rk,0,sizeof(rk));
    for(int i=1;i<maxn;i++)
        fa[i] = i;
    int ans = 0,now = -1;
    for(int i=0;i<tot;i++){
        int from = edge[i].from;
        int to = edge[i].to;
        bool flag = union_set(from,to);
        if(flag && now != edge[i].cost){
            ++ans;
            now = edge[i].cost; 
        }
    }
    cout<<ans<<endl;
}

int main(){
    IO;
    init();
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,cost;
        cin>>u>>v>>cost;
        addedge(u,v,cost);
    }
    sort(edge,edge+tot);
    solve();
    return 0;
}

我想对千千说~