首页 > 其他分享 >国王的烦恼

国王的烦恼

时间:2024-05-14 13:12:55浏览次数:16  
标签:pre bridge int 抗议 烦恼 小岛 天数 国王

描述

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

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

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

输入

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

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

数据规模和约定:

对于30%的数据,1<=n<=20,1<=m<=100;

对于50%的数据,1<=n<=500,1<=m<=10000;

对于100%的数据,1<=n<=10000,1<=m<=100000,1<=a, b<=n, 1<=t<=100000。

输出

输出两个整数a,b,表示居民们会在第a天开始,抗议的天数为b。

样例输入

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

样例输出

2 2

提示

第一天后2和3之间的桥不能使用,不影响。
第二天后1和2之间,以及1和3之间的桥不能使用,居民们会抗议。
第三天后3和4之间的桥不能使用,居民们会抗议。

参考资料:

【蓝桥杯】 历届试题 国王的烦恼(并查集)_c国由n个小岛组成,为了方便小岛之间联络,c国在小岛间建立了m座大桥,每座大桥连接-CSDN博客

思路

若前一天桥断了,会抗议,但后一天就不会了

此题和蓝桥杯的不同点在于还要输出输出开始抗议的天数
此题我们要逆序,即从桥使用天数最久,开始遍历,模拟建桥过程
当有两座桥使用天数相同时,抗议天数只需加 1即可,所以引入lastDay
引用lastDay是为了记录前一次某个桥使用天数,如果当前桥使用天数与lastDay不同,并且将当前桥连接的两座小岛进行merge操作后确实使两座小岛的代表元发生改变,就说明此时需要执行ans++(ans代表抗议天数)

code

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
typedef pair<int, int> PII;
int pre[maxn];
struct Bridge {
	int a, b;
	int day;
}bridge[maxn];

void init() {
	for (int i = 1; i < maxn; i++) {
		pre[i] = i;
	}
}
int find(int x) {
	return pre[x] == x ? x : pre[x] = find(pre[x]);
}
bool merge(int x, int y) {
	int rootx = find(x);
	int rooty = find(y);
	if (rootx != rooty) {
		pre[rootx] = rooty;
		return true;
	}
	return false;
}
bool cmp(Bridge& a, Bridge& b) {
	return a.day > b.day;
}
int main()
{
	int n, m;
	while (cin >> n >> m) {//操作数
		init();
		for (int i = 1; i <= m; i++) {
			cin >> bridge[i].a >> bridge[i].b >> bridge[i].day;
		}
		sort(bridge + 1, bridge + 1 + m, cmp);
		int start = 0, ans = 0, lastday = 0;//start记录抗议开始,ans记录抗议天数,lastday为上一天
		int j = -1;//标记是否开始抗议
		for (int i = 1; i <= m; i++) {
			bool flag = merge(bridge[i].a, bridge[i].b);
         //若两座小岛已通过其他桥梁连接,merge返回false
			if (flag&& bridge[i].day != lastday) {
              //当 bridge[i].day 不等于 lastday 时,意味着这是一个新的抗议天数,因为之前没有桥在这一天失效。
				ans++;
				lastday = bridge[i].day;
			}
			else {
				if (j == -1) {//抗议尚未开始
					start = bridge[i].day;
                 //bridge[i].day表示能够能够使用这座桥最后一天 
					j = 1;
				}
			}
		}
		cout << start << " " << ans << endl;
	}
	return 0;
}

标签:pre,bridge,int,抗议,烦恼,小岛,天数,国王
From: https://www.cnblogs.com/6Luffy6/p/18191068

相关文章

  • 使用 AI 生成正则表达式,告别正则烦恼
    如果你有处理正则表达式的需求,那么这个网站(autoregex.xyz)一定要收藏好。可以根据文字描述生成正则表达式。默认是从文字到正则,不用选择。输入框中输入描述,点击”GO“按钮。等待一会儿,即可生成正则表达式。还可以解析给定的正则,说明其含义。切换成从正则到文字,然......
  • ACwing1064. 小国王
    线性状压DP#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#include<cmath>#include<vector>#defineR(x)x=read()#defineFor(i,j,n)for(inti=j;i<=n;++i)usingnamespacestd;......
  • 报名参加2024CBTC上海国际储能技术展览会,助您拓客爆单没烦恼!
    随着市场饱和度的增加和消费者行为的改变,企业现在获客变得越来越艰难了。目前的市场上,竞争变得越来越激烈,消费者对于品牌的选择和产品的采购也变得更加挑剔和谨慎,更注重品牌的声誉和口碑。因此,企业参展的目的和效率也越来越显而易见。在当下的大环境下,参加展览会是企业进行品......
  • 快递员的烦恼【华为OD机试JAVA&Python&C++&JS题解】
    一.题目-快递员的烦恼快递公司每日早晨,给每位快递员推送需要送到客户手中的快递以及路线信息,快递员自己又查找了一些客户与客户之间的路线距离信息,请你依据这些信息,给快递员设计一条最短路径,告诉他最短路径的距离。注意:不限制快递包裹送到客户手中的顺序,但必须保证都送......
  • OD C卷 - 快递员的烦恼
    快递员的烦恼(200)保证快递送到客户手中,不限制先后顺序;所有快递送完后,快递员还需要回到投递站(只有一个);投递站与客户之间都有路线,但客户与客户之间不一定有路线;投递站、客户位置均允许多次经过;输入描述:首行输入两个正整数n,m;下面n行,输入快递信息,格式为客户id投递站到该......
  • 【题解】A18535.来自领导的烦恼
    题目跳转思路:本题可以使用动态规划或递归的方式来实现,本质上是一道01背包的变型题。假设一共有\(n\)名员工,每一位员工的技能水平用\(a[i]\)表示。要使得两个部门的员工技能总和之差最小,意思就是尽可能地将一个部门的技能之和”凑“到\(\sum\limits_{i=1}^{n}a[i]\times\frac{1}......
  • P2163 [SHOI2007] 园丁的烦恼 题解
    题目链接:园丁的烦恼挺经典的题目,转化成二维数点去做这玩意和常规的偏序计数问题有区别:转化为求\(a\lex\leb\\&\&\c\ley\led\)的数量,这种就别想着拆来拆去了,这种权值类带偏序计数类问题,是经典的可差性问题,我们计:\(ans(x,l,r)\)表示\(t\lex,l\ley\ler\)的数......
  • 每日一题 第三期 洛谷 国王游戏
    [NOIP2012提高组]国王游戏题目描述恰逢H国国庆,国王邀请nnn位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写......
  • 小铃的烦恼
    很显然,这道题目可以借助“分手是祝愿”这道题目的思想,设出\(f[i]\)表示当前状态有\(i\)个最终状态的字符,达到最终状态的期望步数然后我们就开开心心地写出以下方程A_{i}1A_{n-i}1\[f[i]=1+\frac{A_{n-i}^2}{A_n^2}f[i]+\frac{A_{i}^2}{A_n^2}f[i]+\frac{\sump}{A_n^2}f[i+1]+\f......
  • 喜欢的音乐太多了 占用太多内存让电脑卡顿了怎么办?教你一键压缩 帮你搞定烦恼
    下载了很多音乐,发现真的太占空间了,但是又不舍得删除,该怎么办呢?其实我们可以压缩一下,对于喜欢听歌的小伙伴来说,手机里一定存了很多音乐吧,由于手机的存储空间有限,存的音乐越多,手机可用的空间就越小。为了解决手机里音频文件占用空间过大的问题,我们可以将手机里的音频进行压缩,这样......