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

    ID: 235 Type: Default 1000ms 512MiB Tried: 23 Accepted: 6 Difficulty: 8 Uploaded By: Tags>图论上下界网络流最小割退群杯

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

题目背景

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 个整数 a1,a2,,an(i,1ai109)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: 幽灵子弹篇播出。 ↩︎