首页 > 代码库 > nyoj925_国王的烦恼_并查集
nyoj925_国王的烦恼_并查集
国王的烦恼
时间限制：3000 ms | 内存限制：65535 KB
难度：2
- 描述
C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起发起抗议。
现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们一共会发起多少次抗议。
- 输入
- 多组测试数据。
每组数据先输入两个正整数n和m。
接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。（1≤n≤10000,1≤m≤100000，1<=a,b<=n，1≤t≤100000） - 输出
- 输出一个整数，表示居民们发起抗议的次数。
- 样例输入
4 41 2 21 3 22 3 13 4 3
- 样例输出
2
- 提示
- 对于样例：
第一天后2和3之间的桥不能使用，不影响。
第二天后1和2之间，以及1和3之间的桥不能使用，居民们会抗议。
第三天后3和4之间的桥不能使用，居民们会抗议。 - 来源
- 蓝桥杯
- 上传者
- TC_李远航
- 解题思路：前几天做，怎么都不会做，看解题报告也不懂，隔了两天，再看竟然懂了。
- 不过做的很费劲，写完代码后很长时间用在了改代码上。
- 这个题本来是断一个桥就抗议一次。
- 如果反过来想就是修建一座桥，如果天数与前一天不相等，并且这两个桥之间并不相连(这是判断条件)，那么就抗议一次。这些情况正好和断桥时抗议的情况都是一致的。
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int n[10005];struct node{ int u; int v; int w;};node a[100005];int cmp(node aa,node bb){ return aa.w<bb.w;}int find_f(int o){ if(n[o]!=o) n[o]=find_f(n[o]); return n[o];}int union_t(int x,int y){ int fx=find_f(x); int fy=find_f(y); if(fx!=fy){ n[fx]=fy; return 1; }else{ return 0; }}int main(){ int nn,mm;while(~scanf("%d %d",&nn,&mm)){ for(int i=0;i<mm;i++){ if(i>=1&&i<=nn){ n[i]=i; } scanf("%d %d %d",&a[i].u,&a[i].v,&a[i].w); } //if(nn==1){ // printf("0\n"); // return 0; //} if(nn==mm){ n[nn]=nn; } sort(a,a+mm,cmp); int cou=0; int cou1=-99999; for(int i=mm-1;i>=0;i--){ if(union_t(a[i].u,a[i].v)&&a[i].w!=cou1){ cou++; cou1=a[i].w; } } printf("%d\n",cou);} return 0;}
nyoj925_国王的烦恼_并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。