P5008 逛庭院

    • 113通过
    • 713提交
  • 题目提供者 一扶苏一
  • 评测方式 云端评测
  • 标签 强连通分量,缩点 期望 贪心 O2优化
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    你在尘世中辗转了千百年

    却只让我看你最后一眼

    火光描摹容颜燃尽了时间

    别留我一人,孑然一身

    凋零在梦境里面。

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

    题目描述

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

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


    以下是题面内容

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

    画师的庭院可以抽象成一个有向图,每个点代表着一个着火的位置。为了量化火势的大小,扶苏给每个点一个火力值,火力值越大,代表这个点的火势越强。风助火势,火借风力,对于每一个着火点,都有可能因为大风使得火扩散到其他点。有向图的每条边$<u,v>$代表大火是从点$u$扩散到点$v$的。需要注意的是一个点可能会扩散到很多点,也可能是由很多点的大火一起扩散成的。为了不因为灭掉火源让画师发现有人在帮他灭火,在任意时刻,扶苏不能灭掉任何一个不被任何点所扩散的点的火。一个点的火被灭掉后,所代表该点的火扩散的所有边将消失。需要说明的是,虽然边消失了,但是该点扩散到的所有点属性除入度以外都不会改变,更不会消失。

    因为穿越的时间有限,扶苏只能灭掉最多$k$个点的火。因为他菜的马上就要退役了所以他不知道最优方案是什么。于是他想问问你他最多能扑灭多少火力值。

    说人话:

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

    输入输出格式

    输入格式:

    输入的第一行是两个数$n,m,k$,代表图的点数和边数以及点数的限制

    输入的第二行是$n$个整数,第$i$个数代表点$i$的火力值(点权)

    下面$m$行每行两个数$u,v$,代表一条由$u$指向$v$的有向边

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    7 7 3
    10 2 8 4 9 5 7
    1 2
    1 3
    1 4
    2 5
    3 6
    3 7
    4 7
    输出样例#1: 复制
    24

    说明

    本题采用多测试点捆绑测试

    各测试点数据范围与约定如下图所示

    qwq

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。