列表

详情

NC222737. 呜米喵想要成为爱抖露！

描述

这一天MeUmy的大草原上突然出现了一个anti，他用了一个奇怪的装置把呜米的直播账号给锁住了。并留下说明书后光速跑路！
解锁账号有两种方法！
一、
这个装置上有一个地图，上面有n座城市。还有一张数据表,表内有m条数据，表示了每个城市之前存在的交通路线，格式为三个整数A B C  代表A城市到B城市需要花费C元。 (路是双向的 出题人没见过单向的路....)
呜米需要用这些连接方式把所有城市连在一起，连接城市需要用到的交通路线的总花费小于K元，才能解锁自己的账号。
二、
只要呜米去翻垃圾桶，然后喝长毛的的奶茶。账号就会自动解锁！！！

因为呜米不想用第二方法，所以她把城市进行了编号1-n，然后把交通路线的数据发到了群里。求救！
这时一位gachi看不下去了，他对这个装置进行了改造，但是他比那个anti弱所以没办法直接解开，不过在他的不懈努力之下这个装置终于被他搞出了BUG。
本来这个装置在呜米连接好所有城市后会计算总花费。但因为那个bug导致这个装置，会把费用是质数的边当做费用为0。
比如A B C，代表A城市到B城市需要花费C元，C如果是质数，在用的时候费用算作0。
所以第一个方法完成的难度降低了。


输入描述

第一行三个整数 n m k
 
以下m行每行三个整数 A B C
  

输出描述

如果第一种方法可以解锁账号 请输出：wmmxycwdjdwdlnljbzwtskirakira
本来应该输出这个但是qcjj说中文会炸（呜米喵想要成为大家的爱抖露 努力进步在舞台上kirakira）

如果需要第二种方法解锁账号 请输出：wmmxycwdjdwdlnljbzwtsfljt
本来应该输出这个但是qcjj说中文会炸（呜米喵想要成为大家的爱抖露 努力进步在舞台上翻垃圾桶）

示例1

输入: 

5 2 8
2 2 38
4 5 16

输出: 

wmmxycwdjdwdlnljbzwtsfljt

说明:

这组样例有彩蛋.jpg

示例2

输入: 

5 6 30
1 2 10
4 5  9
2 3  5
3 1 11
3 4  7
3 5 20

输出: 

wmmxycwdjdwdlnljbzwtskirakira

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 421ms, 内存消耗: 46684K, 提交时间: 2021-07-12 13:46:42 

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int M=1e7+10;
struct ppp{
	int a,b,c;
}d[N];
int n,m,kk,f[N],k[M];
bool cmp(ppp q,ppp p){
	return q.c<p.c;
}
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
int main(){
	cin>>n>>m>>kk;
	k[1]=0;
	for(int i=2;i<=M;i++){
		if(k[i])continue;
		for(int j=1;j*i<=M;j++){
			k[i*j]=i;
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&d[i].a,&d[i].b,&d[i].c);
		if(k[d[i].c]==d[i].c)d[i].c=0;
	}
	sort(d+1,d+1+m,cmp);
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	int s=0;
	long long int ans=0;
	for(int i=1;i<=m;i++){
		int x=find(d[i].a),y=find(d[i].b);
		if(x==y)continue;
		f[x]=y;
		s++;
		ans+=d[i].c;
		if(s==n-1)break;
	}
	if(ans<kk&&s==n-1)printf("wmmxycwdjdwdlnljbzwtskirakira\n");
	else printf("wmmxycwdjdwdlnljbzwtsfljt\n");
}

上一题

© 2025 nowcoder.com