AT_abc214_h [ABC214H] Collecting

题目描述

有一个包含 $N$ 个顶点、$M$ 条边的有向图。
顶点编号为 $1,\dots,N$，第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$。

一开始，第 $i$ 个顶点上有 $X_i$ 个遗失物品。现在有 $K$ 个人要去捡这些遗失物品。

$K$ 个人会依次在图上移动。每个人的行动如下：

• 从顶点 $1$ 出发，沿着边任意次移动。每到达一个顶点（包括顶点 $1$），如果该顶点上的遗失物品还没有被捡走，则全部捡走。

请你求出最多可以捡到多少个遗失物品。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$ $K$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$
$X_1$ $\ldots$ $X_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 5 2
1 2
2 3
3 2
1 4
1 5
1 4 5 2 8

输出 #1

18

输入输出样例 #2

输入 #2

3 1 10
2 3
1 100 100

输出 #2

1

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq K \leq 10$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$
• 如果 $i \neq j$，则 $A_i \neq A_j$ 或 $B_i \neq B_j$
• $1 \leq X_i \leq 10^9$
• 所有输入均为整数。

样例解释 1

两个人可以按如下方式行动，最多捡到 $18$ 个遗失物品。

• 第一个人按 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ 的顺序移动，捡走顶点 $1, 2, 3$ 上的遗失物品。
• 第二个人按 $1 \rightarrow 5$ 的顺序移动，捡走顶点 $5$ 上的遗失物品。
  无法捡到超过 $19$ 个遗失物品，因此输出 $18$。

由 ChatGPT 4.1 翻译