102147: [AtCoder]ABC214 H - Collecting
Description
Score : $600$ points
Problem Statement
There is a directed graph with $N$ vertices and $M$ edges.
The vertices are numbered $1, \dots, N$, and the $i$-th edge $(1 \leq i \leq M)$ goes from Vertex $A_i$ to Vertex $B_i$.
Initially, there are $X_i$ items on Vertex $i$ $(1 \leq i \leq N)$ that someone has lost. $K$ people will collect these items.
The $K$ people will travel in the graph one by one. Each person will do the following.
- Start on Vertex $1$. Then, traverse an edge any finite number of times. For each vertex visited (including Vertex $1$), collect all items on it if they have not been collected yet.
Find the maximum total number of items that can be collected.
Constraints
- $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$
- $A_i \neq A_j$ or $B_i \neq B_j$, if $i \neq j$.
- $1 \leq X_i \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $K$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$ $X_1$ $\ldots$ $X_N$
Output
Print the answer.
Sample Input 1
5 5 2 1 2 2 3 3 2 1 4 1 5 1 4 5 2 8
Sample Output 1
18
The two people can collect $18$ items as follows.
- The first person goes $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ and collects the items on Vertices $1$, $2$, and $3$.
- The second person goes $1 \rightarrow 5$ and collects the items on Vertex $5$.
It is impossible to collect $19$ or more items, so we should print $18$.
Sample Input 2
3 1 10 2 3 1 100 100
Sample Output 2
1
Input
题意翻译
$n$ 个点 $m$ 条边的有向图,点 $i$ 有 $a_i$ 个物品,$K$ 个人依次从 $1$ 开始遍历这个图。 所到之处收集所有物品,问 $K$ 个人最多收集的物品。 $n,m≤2×10^5,K≤10$Output
问题描述
有一个有向图,包含 N 个顶点和 M 条边。
顶点编号为 1, \dots, N ,第 i 条边 $(1 \leq i \leq M)$ 从顶点 A_i 连接到顶点 B_i。
起初,有人在顶点 i $(1 \leq i \leq N)$ 上遗失了 X_i 件物品。将有 K 个人收集这些物品。
这 K 个人将按照顺序在图中旅行。每个人将执行以下操作。
- 从顶点 1 开始。然后,任意次数地跨越边。对于每个访问过的顶点(包括顶点 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$
- $A_i \neq A_j$ 或 $B_i \neq B_j$,如果 $i \neq j$。
- $1 \leq X_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入将从标准输入以以下格式给出:
$N$ $M$ $K$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$ $X_1$ $\ldots$ $X_N$
输出
打印答案。
样例输入 1
5 5 2 1 2 2 3 3 2 1 4 1 5 1 4 5 2 8
样例输出 1
18
这两个人可以通过以下方式收集到 18 件物品。
- 第一个人走 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ 并收集顶点 1、2 和 3 上的物品。
- 第二个人走 $1 \rightarrow 5$ 并收集顶点 5 上的物品。
无法收集到 19 件或更多物品,所以我们应该打印 18。
样例输入 2
3 1 10 2 3 1 100 100
样例输出 2
1