luogu#P5008. [yLOI2018] 锦鲤抄
[yLOI2018] 锦鲤抄
题目背景
你在尘世中辗转了千百年,
却只让我看你最后一眼。
火光描摹容颜燃尽了时间,
别留我一人,孑然一身,凋零在梦境里面。
—— 银临 & 云の泣《锦鲤抄》
本题原名《逛庭院》。
这首歌的文案如下:(注:不阅读文案不影响下面的阅读)
宁武皇仁光九年锦文轩刻本《异闻录》载:扶桑画师浅溪,居泰安,喜绘鲤。院前一方荷塘,锦鲤游曳,溪常与嬉戏。
其时正武德之乱,藩镇割据,战事频仍,魑魅魍魉,肆逆于道。兵戈逼泰安,街邻皆逃亡,独溪不舍锦鲤,未去。
是夜,院室倏火。有人入火护溪,言其本鲤中妖,欲取溪命,却生情愫,遂不忍为之。翌日天明,火势渐歇,人已不见。
溪始觉如梦,奔塘边,但见池水干涸,莲叶皆枯,塘中鲤亦不知所踪。
自始至终,未辨眉目,只记襟上层迭莲花,其色魅惑,似血着泪。
后有青岩居士闻之,叹曰:魑祟动情,必作灰飞。犹蛾之投火耳,非愚,乃命数也。
题目描述
扶苏被画师和锦鲤的故事深深地打动了。为了能让锦鲤和画师继续生活在一起,他决定回到着火的庭院中灭掉大火。
画师的庭院可以抽象成一个有向图,每个点代表着一个着火的位置。为了量化火势的大小,扶苏给每个点一个火力值,火力值越大,代表这个点的火势越强。
风助火势,火借风力,对于每一个着火点,都有可能因为大风使得火扩散到其他点。有向图的每条边 代表大火是从点 扩散到点 的。需要注意的是一个点可能会扩散到很多点,也可能是由很多点的大火一起扩散成的。
为了不因为灭掉火源让画师发现有人在帮他灭火,在任意时刻,扶苏不能灭掉任何一个不被任何点所扩散的点的火。一个点的火被灭掉后,所代表该点的火扩散的所有边将消失。需要说明的是,虽然边消失了,但是该点扩散到的所有点属性除入度以外都不会改变,更不会消失。
因为穿越的时间有限,扶苏只能灭掉最多 个点的火。他想问问你他最多能扑灭多少火力值。
简化版题意:
给你一张有向图,每个点有一个点权。任意时刻你可以任意选择一个有入度的点,获得它的点权并把它和它的出边从图上删去。最多能选择 个点,求最多能获得多少点权。
输入格式
输入的第一行是三个用空格隔开的整数,代表图的点数 和边数 以及点数的限制 。
输入的第二行是 个用空格隔开的整数,第 个数 代表点 的火力值(点权)。
第 到第 行,每行两个用空格隔开的整数 ,代表一条 指向 的有向边。
输出格式
输出一行一个整数,代表最大的火力值。
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 解释
选择 三个节点。
数据规模与约定
本题采用多测试点捆绑测试,共有 个子任务。
- Subtask 1(30 points):,。
- Subtask 2(30 points):,。保证给出的图是一个有向无环图。
- Subtask 3(20 points):,。保证给出的图中,没有入度的点有且仅有一个。
- Subtask 4(17 points):,。
- Subtask 5(3 points):,。
对于全部的测试点,保证 ,,,。
不保证给出的图没有自环。
提示
- 请注意数据读入对程序效率造成的影响。
- 的末位数字可以帮助你快速的判断测试点所在的子任务。