luogu#P5008. [yLOI2018] 锦鲤抄

[yLOI2018] 锦鲤抄

题目背景

你在尘世中辗转了千百年,
却只让我看你最后一眼。
火光描摹容颜燃尽了时间,
别留我一人,孑然一身,凋零在梦境里面。

—— 银临 & 云の泣《锦鲤抄》

本题原名《逛庭院》。

这首歌的文案如下:(注:不阅读文案不影响下面的阅读)

宁武皇仁光九年锦文轩刻本《异闻录》载:扶桑画师浅溪,居泰安,喜绘鲤。院前一方荷塘,锦鲤游曳,溪常与嬉戏。
其时正武德之乱,藩镇割据,战事频仍,魑魅魍魉,肆逆于道。兵戈逼泰安,街邻皆逃亡,独溪不舍锦鲤,未去。
是夜,院室倏火。有人入火护溪,言其本鲤中妖,欲取溪命,却生情愫,遂不忍为之。翌日天明,火势渐歇,人已不见。
溪始觉如梦,奔塘边,但见池水干涸,莲叶皆枯,塘中鲤亦不知所踪。
自始至终,未辨眉目,只记襟上层迭莲花,其色魅惑,似血着泪。
后有青岩居士闻之,叹曰:魑祟动情,必作灰飞。犹蛾之投火耳,非愚,乃命数也。

题目描述

扶苏被画师和锦鲤的故事深深地打动了。为了能让锦鲤和画师继续生活在一起,他决定回到着火的庭院中灭掉大火。

画师的庭院可以抽象成一个有向图,每个点代表着一个着火的位置。为了量化火势的大小,扶苏给每个点一个火力值,火力值越大,代表这个点的火势越强。

风助火势,火借风力,对于每一个着火点,都有可能因为大风使得火扩散到其他点。有向图的每条边 <u,v><u,v> 代表大火是从点 uu 扩散到点 vv 的。需要注意的是一个点可能会扩散到很多点,也可能是由很多点的大火一起扩散成的。

为了不因为灭掉火源让画师发现有人在帮他灭火,在任意时刻,扶苏不能灭掉任何一个不被任何点所扩散的点的火。一个点的火被灭掉后,所代表该点的火扩散的所有边将消失。需要说明的是,虽然边消失了,但是该点扩散到的所有点属性除入度以外都不会改变,更不会消失。

因为穿越的时间有限,扶苏只能灭掉最多 kk 个点的火。他想问问你他最多能扑灭多少火力值。

简化版题意:

给你一张有向图,每个点有一个点权。任意时刻你可以任意选择一个有入度的点,获得它的点权并把它和它的出边从图上删去。最多能选择 kk 个点,求最多能获得多少点权。

输入格式

输入的第一行是三个用空格隔开的整数,代表图的点数 nn 和边数 mm 以及点数的限制 kk

输入的第二行是 nn 个用空格隔开的整数,第 ii 个数 wiw_i 代表点 ii 的火力值(点权)。

33 到第 (m+2)(m + 2) 行,每行两个用空格隔开的整数 u,vu, v,代表一条 uu 指向 vv 的有向边。

输出格式

输出一行一个整数,代表最大的火力值。

7 7 3
10 2 8 4 9 5 7
1 2
1 3
1 4
2 5
3 6
3 7
4 7
24

提示

样例输入输出 1 解释

选择 3,5,73, 5, 7 三个节点。


数据规模与约定

本题采用多测试点捆绑测试,共有 55 个子任务

  • Subtask 1(30 points):n=10n = 10m=50m = 50
  • Subtask 2(30 points):n=100001n = 100001m=500001m = 500001保证给出的图是一个有向无环图
  • Subtask 3(20 points):n=100002n = 100002m=500002m = 500002。保证给出的图中,没有入度的点有且仅有一个。
  • Subtask 4(17 points):n=100003n = 100003m=500003m = 500003
  • Subtask 5(3 points):n=500004n = 500004m=2000004m = 2000004

对于全部的测试点,保证 1n5×105+41 \leq n \leq 5 \times 10^5 + 41m2×106+41 \leq m \leq 2 \times 10^6 + 40wi1030 \leq w_i \leq 10^30kn0 \leq k \leq n

不保证给出的图没有自环。


提示

  • 请注意数据读入对程序效率造成的影响。
  • nn 的末位数字可以帮助你快速的判断测试点所在的子任务。