221 . 逃脫大戰

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

ioicamp ioicamp-2021

Description

現在你在一個國家，這個國家有 $N$ 個城鎮，編號為 $1, 2, \dots, N$ 。

現在，有 $K$ 個人要從城鎮 $1$ 出發，逃離到城鎮 $N$ 。他們可以藉由 $M$ 條道路來逃離。第 $i$ 條單向路可以讓那些人從城鎮 $u_i$ 到城鎮 $v_i$ 。但是，第 $i$ 條路只能讓 $f_i$ 個人經過，並且每當一個人經過時，需要徵收 $c_i$ 塊過路費。

除此之外，每個城鎮也有容量上限。第 $i$ 個城鎮最多只能讓 $w_i$ 個人經過。

現在，請問最多有多少人可以成功停在城鎮 $N$ ，以及在這個情況下，最小需要繳交多少過路費。

注意 Hint 有帥哥總召送給大家的東西（？）

Input Format

輸入的第一行包含三個整數 $N, M, K$ ，代表城鎮個數、邊的個數，以及人數。

接下來的一行，包含 $N$ 個整數 $w_1, w_2, \dots, w_N$ 。$w_i$ 代表城鎮 $i$ 可以被經過的人數。

接下來的 $M$ 行，每行包含四個整數 $u_i, v_i, c_i, f_i$ ，意義已經在題目敘述中敘述過了。

  • $2 \leq N \leq 100$
  • $0 \leq M \leq 100$
  • $1 \leq K \leq 100$
  • $1 \leq u_i, v_i \leq N$
  • $1 \leq c_i, f_i \leq 100$

Output Format

輸出兩個整數於一行。第一個整數代表最多有多少人可以停在城鎮 $N$ ，以及在這個情況下，最少要花多少過路費。

Sample Input 1

3 4 4
5 5 5
1 2 3 5
1 2 2 2
2 3 3 1
1 3 2 6

Sample Output 1

4 18

Hints

有一天，你撿到了一張報紙，報紙內容如下：
「
最後的個人賽
小明超級厲害
花了兩個小時
費氏數列ＡＣ
最後的個人賽
大明有點品祥
流水題不ＡＣ
」

Problem Source

IOICamp 2021 Day4 pE

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~15 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
Submit
Back to Top