A. A. ‘Asada Shino’ KSkun 和他的卧底战术

    Type: Default 1000ms 512MiB

A. ‘Asada Shino’ KSkun 和他的卧底战术

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

2077 年 1 月 1 日,人类迎来了他们在 56 年前被很多人戏称为赛博朋克时代的新年。然而赛博朋克并没有到来。

里泰尔德的夜晚是黏稠的,黑暗被随处可见的泛光灯侵蚀,却又裹挟着这俗套至极的处处喧嚣。55 年过去,没有彻底的两极分化,没有绝望的 high tech low life,但散落在这个城市的,是那些曾经在小说里一次次出现、一遍遍重复的情节。

没错,2077 年的世界——已经被人类创作的小说组成的一个个下层叙事所污染了。

KSkun 神色迷茫地漫步在商圈中心附近的街道上。距离他来到这个世界已经过去了大约 30 分钟,他也在街上流浪了 30 分钟。他似乎还没能完全接受已经穿越的事实,不够可能更让他无法接受的是——他已经变成了朝田诗乃的模样。

是的,就是 63 年前[1]他在 B 站上见过的那个诗乃。

他后来意识到,穿越成美少女本身可能也是这个世界的认知危害之一。只是现在,他仍然无法从这种剧变中缓过神来。

但有人想帮他。

一辆警用摩托车停在他的面前。警察跨下车,摘下头盔,走到了他的面前。2077年的摩托车外观上还是能看出几十年前的设计痕迹,就连头盔也是一样。不过,就实际使用效果来说或许提升了不少。

“小姑娘,这大半夜的,别在这种地方一个人晃悠了,早点回去吧。”

“......”

“你家在哪啊?”

“......”

“喂?”

他终于无法控制内心的烦躁,一记右拳砸向那个警察的面部。警察下意识地伸起胳膊,但谁也没想到的是,这记拳头如同一记重锤直接把他击倒在地,他抽搐了下,便再无声息,大概没个半天是醒不过来了。

“??”

KSkun 有点惊讶地望着他的拳头。他意识到自己好像整了个大活,但还没等他想出逃跑的方案,一辆黑色的越野车就从前方飞速驶来,然后在他的旁边停下。

车门打开,一个胡子拉碴的国字脸中年男人走出。

“你好,同志。自我介绍一下,我们是龙组。”

题目描述

KS 来到里泰尔德的这段日子实在不太顺利。虽然在龙组的这一个礼拜算是接受了种种魔幻的事实,但他对这个俗套的设定无法再吐槽更多。

为了拯救自己被毁掉的三观,也为了调查清楚这个世界和自己穿越的真相,KS 打算利用这次机会,潜伏在龙组内 (当然这只是他给自己的 idea 取的好听一点的名字,实际上无论他现在想干啥他都只能呆在龙组) ,打探尽可能多的情报,同时找到离开的办法。

经过一周的调查,KS 将龙组的人员体系摸了个大概。凭借着诗乃的计算能力和自己身上多出来的莫名其妙的力量(也有可能还是诗乃的),他打算制定一套多线出击的战术。

龙组的每个成员都有一个情报价值 aia_i,表示 KS 打倒这个成员之后会获得相当于 aia_i 价值的情报。同时他们之间的上下级关系构成了一个 nn 个点 mm 条边的有向无环图:每个点代表一个成员;如果存在一条从某个点 uu 到另一个点 vv 的路径,则 uu 号成员就是 vv 号成员的上级。

虽然潜行的要义就是杀光,但 KS 目前也不能贸然行动。他打算先选择若干个龙组成员并同时下手,打倒他们后拿到一些情报。KS 希望他获得的情报总价值越高越好,但如果 KS 同时打倒了两个具有上下级关系的成员,就会引起龙组的注意,从而让他的计划失败。

因此,KS 希望在动手之前知道他在此次行动中能获得的情报总价值的最大值,同时他还打算找到一组可以选择的目标。而作为龙组的老大,你也很想知道。

数据格式与约定

输入

输入第一行包含两个整数 n(1n2×104)n (1 \le n \le 2\times 10^4)m(1m5×104)m (1 \le m \le 5\times 10^4),表示成员数和关系条数。

接下来一行包含 nn 个整数 $a_1, a_2, \dots, a_n (\forall i, 1 \le a_i \le 10^9)$,表示打倒每个成员可以获得的情报价值。

接下来 mm 行,每行包含两个整数 uuvv (1u,vn1 \le u, v \le n),表示 uu 号成员是 vv 号成员的直接上级。

输出

输出第一行包含一个整数,表示 KS 能获得的情报总价值的最大值。

接下来若干行,输出一组 KS 可以选择的目标成员编号,可以用任意顺序输出这些编号。如果有多组可行的方案,任选其中一组输出即可。

样例

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

样例解释

对第二组样例,如果你输出了

5
2 3

也会被判定为正确。

后记

“朝田诗乃!朝田诗乃!能听见吗?”

“!!你……你是谁?”

“看来是连上了。其实我不知道你是谁,但你应该不是这个世界的人吧。”

“你入侵我的通讯设备有什么目的?”

“……好吧。自我介绍一下,63 年前我追过以你为女主的新番,叫做《刀剑神域》。我的名字是——kernel.bin。”


  1. 2014 年 7 月 5 日,刀剑神域II: 幽灵子弹篇播出。 ↩︎

「退群杯」3rd

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
10
Start at
2022-2-12 13:30
End at
2022-2-12 18:30
Duration
5 hour(s)
Host
Partic.
205