H - Collecting

Contest Duration: 2021-08-14(Sat) 12:00 - 2021-08-14(Sat) 13:40 (local time) (100 minutes) Back to Home

H - Collecting Editorial

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

$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$ から出発し、辺をたどって移動することを任意の有限回繰り返す。訪れた各頂点（頂点 $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$
入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$2$ 人がそれぞれ次のように行動することで、 $18$ 個の落とし物を拾うことができます。

$1$ 人目は、頂点 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$ の順に移動し、頂点 $1, 2, 3$ にある落とし物を拾う。
$2$ 人目は、頂点 $1 \rightarrow 5$ の順に移動し、頂点 $5$ にある落とし物を拾う。

$19$ 個以上の落とし物を拾うことはできないので、 $18$ を出力します。

入力例 2Copy

Copy

3 1 10
2 3
1 100 100

出力例 2Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

3 1 10
2 3
1 100 100

Sample Output 2Copy

Copy