Applese 的毒气炸弹

2024-06-17 21:38
文章标签 炸弹 applese 毒气

本文主要是介绍Applese 的毒气炸弹,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目描述】

众所周知,Applese 是个很强的选手,它的化学一定很好。

今天他又AK了一套题觉得很无聊,于是想做个毒气炸弹玩。

毒气炸弹需要 k 种不同类型元素构成,Applese一共有 n 瓶含有这些元素的试剂。 

已知元素混合遵循 m 条规律,每一条规律都可以用 "x y c" 描述。

表示将第 x 瓶试剂混入第 y 瓶试剂或者把第 y 瓶试剂混入第 x 瓶试剂,需要消耗 c 的脑力。

特别地,除了这 m 条规律外,Applese 可以将任意两瓶相同元素的试剂混合,且不需要消耗脑力。

Applese 想要配出毒气炸弹,就需要使 S 中含有 1∼k 这 k 种元素。它想知道自己最少花费多少脑力可以把毒气炸弹做出来。

【输入描述】

第一行为三个整数 n, m, k 表示 Applese 拥有的试剂的数量,混合规律的数量和所需的元素种类数。
第二行为 n 个整数 a1,a2,…,an,分别表示每一瓶试剂的元素类型。
接下来m行,每行三个整数 x, y, c,含义如题目描述中所述。不保证 x, y的试剂种类不同。

1≤n,k,m≤10^5
1≤x,y≤n,x≠y
1≤c≤10^9

【输出描述】

输出一个正整数表示最小的耗费脑力。特别地,如果无法合成出毒气炸弹,输出 "-1"。

【样例】

示例1

输入
6 8 2
1 1 1 2 2 2
1 2 1
2 3 2
1 3 3
3 4 6
4 5 1
4 6 3
5 6 2
1 6 2
输出
2

思路:

题目比较绕,读懂题后其实并不难,看成一张图后,其实就是 n 个点 m 条边然后在 k 的限制内求最小生成树

【源代码】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define INF 0x3f3f3f3f
#define N 100001
#define LL long long
const int MOD=1e9+7;
using namespace std;
struct Edge{int x,y;int cost;Edge(){}Edge(int x,int y,int cost):x(x),y(y),cost(cost){}bool operator < (const Edge &rhs)const{return rhs.cost>cost;}
}edge[N];
int n,m,k;
int a[N];
int father[N],num[N];
int Find(int x){if(father[x]==x)return x;return father[x]=Find(father[x]);
}
void Union(int x,int y){x=Find(x);y=Find(y);if(x==y)return;if(num[x]==num[y]){father[y]=x;num[x]++;}else if(num[x]<num[y])father[x]=y;elsefather[y]=x;}
LL kruskal(){sort(edge,edge+m);LL res=0;int cnt=0;for(int i=0;i<m;i++){int x=edge[i].x;int y=edge[i].y;int cost=edge[i].cost;if(Find(x)!=Find(y)){Union(x,y);res+=(LL)cost;if(++cnt==k-1)break;}}return (cnt==k-1?res:-1);
}
int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++)cin>>a[i];for(int i=0;i<m;i++){int x,y,c;cin>>x>>y>>c;edge[i]=Edge(a[x],a[y],c);}memset(num,0,sizeof(num));for(int i=0;i<=n;i++)father[i]=i;cout<<kruskal()<<endl;return 0;
}

 

这篇关于Applese 的毒气炸弹的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070548

相关文章

【每日一题】LeetCode 1652.拆炸弹(数组、滑动窗口)

【每日一题】LeetCode 1652.拆炸弹(数组、滑动窗口) 题目描述 你有一个炸弹需要拆除,时间紧迫!你的情报员会给你一个长度为 n 的循环数组 code 以及一个密钥 k。 为了获得正确的密码,你需要替换掉每一个数字。所有数字会同时被替换。 如果 k > 0,将第 i 个数字用接下来 k 个数字之和替换。如果 k < 0,将第 i 个数字用之前 k 个数字之和替换。如果 k ==

今日算法:蓝桥杯基础题之“星系炸弹”

你好,我是沐爸,欢迎点赞、收藏、评论和关注。 今日算法第4题,如何布置星系炸弹,一起看看吧。 题目 在X星系的广袤空间中漂浮着许多X星人造“炸弹”,用来作为宇宙中的路标。每个炸弹都可以设定多少天之后爆炸。比如:阿尔法炸弹2015年1月1日放置,定时为15天,则它在2015年1月16日爆炸。有一个贝塔炸弹,2024年8月30日放置,定时为1000天,请你计算它爆炸的准确日期。 JS 代码实现

linux bash shell之递归函数:fork炸弹

所谓fork炸弹是一种恶意程序,它的内部是一个不断在fork进程的无限循环,fork炸弹并不需要有特别的权限即可对系统造成破坏。fork炸弹实质是一个简单的递归程序。由于程序是递归的,如果没有任何限制,这会导致这个简单的程序迅速耗尽系统里面的所有资源。下面是Jaromil设计的最简单的fork炸弹: :() { :|:& };: 或者是 .() { .|.& };. 这么一行只有13个字符

pygame—炸弹牌(可做课设)

游戏介绍 在5X5的数字宫格里翻牌,翻出所有的2和3即可获胜每一格只能是0、1、2、3,第六列和最第六行为 X | Y,X代表该列或该行的数字总和,Y代表该列或该行的0的个数控制难度,每行每列的数字总和不超过9该游戏需要一定运气及技巧 核心代码 生成二维数字列表 def createNumList() -> list:arr = []for i in range(6):row = []ro

二进制炸弹的fp是什么?

🏆本文收录于「Bug调优」专栏,主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!! 问题描述   我在解二进制炸弹第四阶段的递归时,对主函数中的片段的理解如下: 8bc4: e3530002 cmp r3, #28bc8:

Applese 的大奖

【题目描述】 Applese 和它的小伙伴参加了一个促销的抽奖活动,活动的规则如下:有一个随机数生成器,能等概率生成 0∼99 之间的整数,每个参与活动的人都要通过它获取一个随机数。最后得到数字最小的 k 个人可以获得大奖。如果有相同的数,那么后选随机数的人中奖。 Applese 自然是最心急的一个,它会抢在第一个去按随机数。请你帮忙计算一下它能够中奖的概率。 【输入描述】 仅一行三个正整数 n

Applese 走迷宫

【题目描述】 精通程序设计的 Applese 双写了一个游戏。 在这个游戏中,它被困在了一个 n×m 的迷宫中,它想要逃出这个迷宫。 在迷宫中,有一些方格是水池,只有当 Applese 处于水属性的时候才可以通过;有一些方格是岩浆,只有当 Applese 是火属性的时候可以通过;有一些方格是墙壁,无论如何都无法通过;另一些格子是空地(包括起点和终点),可以自由通过。 在一些空地上有神秘道具可以让

Applese 涂颜色

【题目描述】 精通程序设计的 Applese 叕写了一个游戏。 在这个游戏中,有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大,你需要将答案对 10^9+7 取模。 【输入描述】 仅一行两个正整数 n, m,表示方阵的大小。 1≤n,m≤10^100000 【输出描述】 输出一个正整数,表示方案数对

Applese 的取石子游戏

【题目描述】 Applese 和 Bpplese 在玩取石子游戏,规则如下: 一共有偶数堆石子排成一排,每堆石子的个数为 ai。两个人轮流取石子,Applese先手。每次取石子只能取最左一堆或最右一堆,且必须取完。最后取得的石子多者获胜。假设双方都足够聪明,最后谁能够获胜呢? 【输入描述】 第一行是一个正偶数 n,表示石子的堆数。 第二行是 n 个正整数 a1,a2,…,an,表示每堆石子的个数

Swift语言:苹果在程序员社区投下的重磅炸弹

6月3日凌晨,苹果WWDC全球开发者大会传来消息,苹果公司在此次大会上丢出重磅炸弹——爆冷推出名为Swift的新语言,此消息一时在程序员群体中炸开了锅,掌握Objective-C语言及正在学习Objective-C语言的程序员们对天长叹,难道末路已到?而微博、微信、论坛上大量调侃的消息亦层出不穷,甚至有网友晒出Objective-C相关学习资料被丢到垃圾桶的照片,总之一时之间Swift语言成为网络