P5008 [yLOI2018] Jinli Chao

> You have wandered in the mortal world for thousands of years, > yet you only let me see you one last time. > Firelight traces your face and burns away time, > do not leave me alone, solitary, withering inside a dream. — Yin Lin & Yun Zhi Qi, *Jinli Chao* The original name of this problem was *Strolling in the Courtyard*. The copywriting of this song is as follows: (Note: not reading it does not affect understanding the problem below.) > The *Records of Strange Tales* (a Jinxuan Hall printed edition) from the ninth year of the Ningwu Emperor Renguang records: A Fusang painter named Qianxi lived in Taian and loved painting koi. Before his house was a lotus pond where brocade koi swam; Xi often played with them. > At that time, the Wu De rebellion was raging, warlords fought each other, wars happened again and again, and monsters ran wild on the roads. When the war approached Taian, neighbors all fled; only Xi stayed, unwilling to leave the koi behind. > That night, the house suddenly caught fire. Someone entered the fire to protect Xi, saying they were a demon from among the koi, originally here to take Xi’s life, yet they developed feelings and could not bear to do so. At dawn the next day, the fire gradually died down, and the person was gone. > Xi then felt it was like a dream, and ran to the pond, only to see the water dried up, lotus leaves all withered, and the koi in the pond were nowhere to be found. > From start to finish, Xi never saw the person clearly, only remembering layered lotus flowers on their collar, enchanting in color, like blood stained with tears. > Later, a hermit called Qingyan heard this and sighed: When an evil spirit falls in love, it must turn to ashes and vanish. It is like a moth flying into the fire—not stupidity, but fate.

Fusu was deeply moved by the story of the painter and the koi. In order to let the koi and the painter continue living together, he decided to return to the burning courtyard and put out the fire. The painter’s courtyard can be abstracted as a directed graph. Each node represents a burning location. To measure the size of the fire, Fusu assigns each node a fire value. The larger the fire value, the stronger the fire at that node. Wind helps the fire, and the fire borrows the wind’s force. For each burning node, strong wind may cause the fire to spread to other nodes. Each directed edge $$ in the graph represents that the fire spreads from node $u$ to node $v$. Note that one node may spread to many nodes, and it may also be formed by fires spreading together from many nodes. To avoid the painter noticing that someone is helping to put out the fire, at any moment, Fusu is not allowed to extinguish the fire at any node that is not being spread to by any node. After a node’s fire is extinguished, all outgoing edges representing the spread from that node will disappear. Note that although the edges disappear, all properties of the nodes that it spreads to, except for their in-degrees, will not change, and they will not disappear. Because the time for time travel is limited, Fusu can extinguish the fire of at most $k$ nodes. He wants to ask you what is the maximum total fire value he can extinguish. #### Simplified statement: Given a directed graph where each node has a weight. At any moment, you may choose any node **with in-degree**, gain its weight, and delete it and its outgoing edges from the graph. You may choose at most $k$ nodes. Find the maximum total weight you can obtain.

The first line contains three integers separated by spaces, representing the number of nodes $n$, the number of edges $m$, and the limit on the number of chosen nodes $k$. The second line contains $n$ integers separated by spaces. The $i$-th integer $w_i$ represents the fire value (node weight) of node $i$. Lines $3$ to $(m + 2)$ each contain two integers $u, v$ separated by spaces, representing a directed edge from $u$ to $v$.

Output one line with one integer, representing the maximum total fire value.

### Explanation for Sample Input/Output 1 Choose nodes $3, 5, 7$. --- ### Constraints **This problem uses bundled testdata with a total of $5$ subtasks**. - Subtask 1 (30 points): $n = 10$, $m = 50$. - Subtask 2 (30 points): $n = 100001$, $m = 500001$. **It is guaranteed that the given graph is a directed acyclic graph.** - Subtask 3 (20 points): $n = 100002$, $m = 500002$. It is guaranteed that in the given graph, there is one and only one node with in-degree $0$. - Subtask 4 (17 points): $n = 100003$, $m = 500003$. - Subtask 5 (3 points): $n = 500004$, $m = 2000004$. For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^5 + 4$, $1 \leq m \leq 2 \times 10^6 + 4$, $0 \leq w_i \leq 10^3$, $0 \leq k \leq n$. It is **not guaranteed** that the given graph has no self-loops. --- ### Notes - Please pay attention to the impact of input reading on program efficiency. - The last digit of $n$ can help you quickly determine which subtask the test point belongs to. Translated by ChatGPT 5