题目名称 2025. 红色警戒4星际穿越
输入输出 Interstellar_Timetravel.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 GravatarSatoshi 于2015-08-19加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:2, 提交:3, 通过率:66.67%
Gravatarraywzy 100 0.163 s 8.57 MiB C++
GravatarSatoshi 100 0.193 s 1.43 MiB C++
Gravatarraywzy 90 0.183 s 8.57 MiB C++
关于 红色警戒4星际穿越 的近10条评论(全部评论)
符合条件时重要度最大,符合啥条件啊?
Gravatar瑆の時間~無盡輪迴·林蔭
2020-04-24 22:01 5楼
没玩过红警看不懂背景呀
Gravatar夜莺
2020-03-01 13:01 4楼
图不错,我喜欢
Gravatar浮生随想
2016-11-05 21:05 3楼
神题刘明...
GravatarAntiLeaf
2016-08-03 18:50 2楼
你们搞的这个题面啊,excited!
赫鲁晓夫看了一下历史,决定首先把中修干掉……
Gravatarcstdio
2015-08-19 18:16 1楼

2025. 红色警戒4星际穿越

★★☆   输入文件:Interstellar_Timetravel.in   输出文件:Interstellar_Timetravel.out   简单对比
时间限制:1 s   内存限制:256 MiB

    一位叫赫鲁耶夫•墨脱娃•弗拉基米尔•弗拉基米罗维奇•切尔诺贝利斯基的苏联复国主义青年启动了时间机器,回到了100年前……

他成功的劝说了当时的领导人赫鲁晓夫,由于知道了未来的历史,赫鲁晓夫决定在被西方资本主义腐朽势力侵蚀之前彻底击垮他们。

苏联一举用核导弹摧毁了美国境内所有的核导弹,接着苏联水路并进,迅速攻占了华盛顿,摧毁了五角大楼和自由女神像,很快美国宣布投降。

    由于失去了美国的影响,西欧的共产主义势力大大加强,无尽的工人起义最终颠覆了西欧各政府。

苏联进占美国航天局NASA,并改名为KATYUSA(喀秋莎),下一步,苏联将把共产主义扩展到全宇宙

由于社会主义的巨大优越性,苏联很快探索了大量的星球,并用重型天启坦克消灭了一些星球上的外星人。

现在,苏联已经控制了n个星球,并且已经探明有m个虫洞可以连接某些星球,为了加强对星球的管理,苏联要在这些虫洞的基础上,建立一个管理网络。

然而苏联的资金是非常紧张的,所以要求使用最少的资金,使任意两个已经探索的星球联通。1单位长度需要1资金

    在建好了管理网络的基础上,苏联高层为了掩饰其没有资金建立许多时空隧道的事实,宣布在已经建好的管理网络互不相邻的两个星球具有“距离美”,每个星球有一个重要值,要求你选出一些星球,使这些星球符合条件时使重要值的和最大

然而如果存在任意两个星球根本不联通,则输出“Long live Soviet!Long live communism!”(苏维埃万岁!共产主义万岁!)

    你曾经是一名辐射工兵,然而随着战争的减少,你转行做了KATYUSA的物理工程师,现在你的全家都被苏联控制了起来,如果你不能完成任务,你的家人就会收到迫害.

【输入格式】:

第一行两个整数n,m

接下来m行每行三个数a,b,c表示a星球和b星球之间存在一个长度为c的虫洞

接下来1行有n个数,表示每个星球的重要度

【输出格式】:

如果不连通,则输出“Long live Soviet!Long live communism!”

否则输出两个数,一个是最少所需的资金另一个是最大重要值和

【输入样例】:

3 3

1 2 1

2 3 2

1 3 1

1 2 1

【样例输出】:

2 3

【样例说明】:

连接虫洞(1,2)(1,3)使(1,2,3)联通需要最少资金1+1=2,所以管理网络为(1,2)(1,3)

由于(2,3)虽然有虫洞,但是管理网络并不经过(2,3),而是经过(1,2)和(1,3),所以(2,3)不相邻,所以最大重要值和为2+1=3

【数据范围】:

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

对于60%的数据,n<=200,m<=10000

对于100%的数据,n<=2000,m<=50000,没有任意两个虫洞长度相同